# Tag Info

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 ...
• 26.6k
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
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 ...
• 26.6k
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,444

### 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

### 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,400
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.3k
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 ...
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,419
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.3k
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 ...
• 1,553

### 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

• 6,659
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,400
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,728
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