As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [approximation]

The tag has no usage guidance.

58 questions
Filter by
Sorted by
Tagged with
1 vote
67 views

### How to enforce convexity?

I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. ...
• 111
115 views

### Approximate inclusion-Exclusion?

I am trying to understand or find literature on the following problem of approximate inclusion exclusion. Let $S:=\{A_i\}_{i=1}^{m}$ be a set of $m$ sets. Every intersection of $k$ elements in $S$ ...
• 706
1 vote
253 views

### State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia: The polynomial-time approximation algorithm for Max-Cut with the best known ...
• 173
1 vote
64 views

### How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

Consider a bimatrix game problem with matrix $A$ and $B$. The definition of the value $v = [v_1, v_2]$ of the Nash equilibrium $(x, y)$ are as follows, $$v_1 = x^TAy,$$ $$v_2 = x^TBy.$$ The situation ...
• 141
62 views

### Set cover where consecutive sets differ by at most one item [closed]

First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
• 230
336 views

### Fastest approximate triangle counting algorithms in dense graphs

One may compute the number of triangles in a graph by matrix multiplication in time $O(n^\omega)$. There is also a very simple algorithm that runs in time $O(n^3/(\epsilon^2 T))$ (where $T$ is the ...
• 610
101 views

### Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm

I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated ...
• 41
1 vote
54 views

### polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
586 views

### Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
• 563
93 views

### Optimization problems with same optimal value, but different approximation behavior

Context: related to this answer. I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense ...
• 1,633
573 views

### If NP in BPP then NP equals RP

I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links: https://cs.stackexchange.com/q/80509 http://www.inf.ed.ac.uk/teaching/...
• 1,217
964 views

### Is an algorithm with an approximation factor of 4000 useful?

A paper published in SODA this year (2019) proposed a constant approximation algorithm for the lower bounded facility location problem with general lower bounds. To my surprise, when reading the ...
229 views

### Martingale exit arguments for gradient Langevin dynamics

I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
• 1,443
79 views

• 1,562
1 vote
645 views

### Approximately counting paths and cycles in a graph

Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. The question is about the approximability of these graph ...
• 1,081
1 vote
133 views

### Does the NP-hardness of finding any valid solution imply NPO-hardness?

Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
177 views

### Universal approximation theorem of second order

The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem) informally states that up to several conditions, any function can be approximated by a shallow ...
• 181
668 views

### Why isn't the Charikar algorithm for finding the densest subgraph optimal?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different ...
• 93
143 views

### Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i?$" for some $i$, taking the left branch means "yes", ...
516 views

### Is there any known Poly-APX-complete minimimization problem?

All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
225 views

### Proof of a (simple) lemma by Aaronson

I am reading this article, and I need help with an apparently obvious proof. The lemma (on page 5), that I want to know the proof of, is this: Let $p : \{0,1\}^N \rightarrow \mathbb{R}$ be a real ...
• 355
175 views

• 11.3k
147 views

• 13
1 vote
232 views

### Is there any research on approximation of reals with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
• 127
1 vote
117 views

### Computing log of sum of positive integers

As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
• 727
120 views

### The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
• 1,224
175 views

### Finding optimal subset for quadratic function

Given a set of $n$ elements $e_1,...e_n$ where each element $i$ is associated with two positive integers $\alpha_i$ and $\beta_i$. Given another integer $\lambda$, the goal is to find a set $S$ of ...
• 11
1 vote
45 views

• 459