# Tag Info

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'|$. ...
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 ...
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 ...
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 ...

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

### 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 ...
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\},~ ...
1 vote
Accepted

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(...
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 ...

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