14
votes
Accepted
Is the following graph optimization problem approximable within a constant factor?
The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. ...
- 3,919
11
votes
Accepted
If NP in BPP then NP equals RP
An actual factual reference is
K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39–43, 1982.
(When I first saw this result --- I ...
- 27.5k
6
votes
Accepted
Is an algorithm with an approximation factor of 4000 useful?
A very good question! While I think a feasible solution which is 4000 times worse than the optimum is often not very practical, if you have several approximation algorithms to choose from, I would ...
- 6,665
4
votes
Accepted
Why isn't the Charikar algorithm for finding the densest subgraph optimal?
Suppose you have a complete graph on four nodes and then next to it a graph with five nodes comprising a degree four hub and four degree 3 satellites. The greedy algorithm might start by removing one ...
- 643
4
votes
Is there any research on approximation of reals with computable numbers
It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ...
- 4,485
4
votes
Accepted
Optimization problems with same optimal value, but different approximation behavior
What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs?
These two problems ...
- 11.6k
3
votes
Accepted
State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson
These are not directly comparable:
Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual ...
- 11.6k
3
votes
Accepted
Proving hardness of approximation with reduction in terms of 1/$\epsilon$
You can think of $\epsilon$ as parametrizing a family of reductions to a family of approximation problems:
The $\epsilon$-th problem is to compute a $1+\epsilon$ approximation to the underlying ...
- 1,429
2
votes
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.
1
vote
How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$
It depends on what your usecase is. If you are interested in getting close to an actual Nash equilibrium, then the quality measure you want will be the distance to the nearest Nash equilibrium (which ...
- 111
1
vote
Accepted
Set cover where consecutive sets differ by at most one item
Take an arbitrary instance $S_1,\ldots,S_n$ of SET COVER. Between $S_1$ and $S_2$, insert a chain of new subsets
$$ S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ ...
- 5,782
1
vote
Accepted
Fastest approximate triangle counting algorithms in dense graphs
I have written up an answer, it can be found here: https://arxiv.org/abs/2104.08501
The best known triangle counting algorithm runs in time $\tilde{O}(n^\omega)$. I was able to retain the exponent of $...
- 630
1
vote
Accepted
Bi-criteria combinatorial approximation algorithms for min k-vertex cover
Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph $G=(V,E)$ and an integer $m' \le |E|$ and the goal is to find a minimum cardinality subset $...
- 7,039
1
vote
Accepted
Examples of nontrivial non-discriminatory functions
Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$.
In particular, Lebesgue measure is $|\mu|$.
...
- 4,485
1
vote
Accepted
How good of an approximate 2-coloring can you get of the halved cube graph?
The answer is $\epsilon_n = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2}$.
First, here's a formal definition of the halved cube graph $H_n$. The vertices are ...
- 2,883
1
vote
Approximately counting paths and cycles in a graph
Approximately counting all paths (or cycles) in polynomial time implies NP=RP. There is a very simple reduction to amplify the weight of the longest path/cycle. See https://doi.org/10.1016/0304-3975(...
- 375
1
vote
Accepted
Is there any known Poly-APX-complete minimimization problem?
I've just discovered there exists at least one confirmed minimization Poly-APX-complete problem: Min ones if setting all variables true satisfies all clauses (together with other conditions). It is ...
- 408
1
vote
Accepted
Looking for approximation class between NPO and Exp-APX
As pointed out by Markus Bläser in the comments section, objective values must be positive integers, so they cannot be 0. Hence my problem A is not formally an NPO problem. Personally I think it makes ...
- 408
Only top scored, non community-wiki answers of a minimum length are eligible