18 votes
Accepted

smallest circuit size using XOR gates

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7 The ...
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,844
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 ...
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 ...
5 votes

Finding optimal subset for quadratic function

For all $\beta_i = 0$, asking whether one can get objective function value $1$ is equivalent to Subset Sum, and therefore NP-complete. Simple reductions from Subset Sum also prove that it is NP-...
  • 3,236
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 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 ...
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 ...
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 ...
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 ...
3 votes
Accepted

Max-cut equivalence with most likely assignment to an Ising model

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute. In the formulation you give for the Ising model, we are trying to ...
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,722
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 $...
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 ...
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 ...
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 $...
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|$. ...
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 ...
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

Only top scored, non community-wiki answers of a minimum length are eligible