# Tag Info

18

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 reduction is from Vertex Cover and is very nice. Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+... 14 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'|$. For brevity, let me call you problem$\cal P$and Min Uncut$\cal U$. Observation. An instance$G$of$\cal P$has a solution of cost 0 if and only if$G$is ... 11 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 don't remember where it was now --- it was called "Ko's Theorem". Googling suggests that another theorem has that name as well...) 8 To complement the other answer: Costello, Shapira and Tetali showed that the expected approximation ration achieved by Johnson's algorithm on a random permutation of the variables is strictly better than$\frac{2}{3}$. Poloczek and Schnitger showed that another randomized version of the algorithm has expected approximation ratio$\frac{3}{4}$, and that the ... 6 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 rather implement the one with a better performance guarantee. Well, maybe not always. At the very least, the feasible solutions found are often of much better ... 6 If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.) Given a graph$G$and an integer$k$, find a subgraph of$G$on$k$nodes with maximum density. Khot proved that no PTAS exists under plausible complexity assumptions; there is an$O(n^{1/...

5

The described algorithm is actually Johnson's algorithm (with order on the vertices) which is known to achieve$\frac{2}{3} ratio$.

5

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-complete to approximate the objective function within any factor polynomial in $n$. We can reduce the $\beta_i = 0$ case to the case where $\beta_i = 1$ by just ...

5

This is the Vector Scheduling (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input: Chekuri, C., Khanna, S.: On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004. The same paper gives a polynomial-time approximation scheme when $d$ is not part of the input, and a polynomial ...

4

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 have the same optimal value. However, if I give you a black-box algorithm that finds a $(1+\epsilon)$-approximation of the minimum fractional vertex cover, this ...

4

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 of the satellites and thus spoil the optimum which is 1.6 o-------o o-------o | \ / | | \ / | | X | | o | | / \ | | / \ | o-------o ...

4

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 papers. See for instance Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization, ZBL06837203.

3

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 optimization problem. The $\epsilon$-th reduction shows that the $\epsilon$-th problem is $\mathrm{NP}$-hard.

3

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 approximation ratio. The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of ...

3

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 maximize $\sum_{ij\in E}\lambda_{ij}x_{ij}$, where $x_{ij}=1$ if $x_i=x_j$ and $x_{ij}=-1$ otherwise. In maximum cut, we take each edge weight $w$ and try to maximize ...

2

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

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 you probably can't compute efficiently). If you are satisfied with approximate equilibria, you should instead use the incentive players have to deviate from the ...

1

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\},~ S_2-\{a\}.$$ Do the same for all other pairs of consecutive sets. The resulting instance satisfies your condition, and it is equivalent (with respect to ...

1

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 $n$ while having negative dependence on $T$. In fact, the running time is $\tilde{O}_\epsilon(n^\omega/T^\delta)$ such that there is the is no such algorithm ...

1

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 shown in "The Approximability of Constraint Satisfaction Problems" by Sanjeev Khannay, Madhu Sudanz, Luca Trevisanx and David P. Williamson (http://people.csail....

1

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 sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining ...

1

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 $S$ of vertices such that they cover at least $m'$ edges. Hence, if $m' = |E|$ we have the usual Vertex Cover problem. A $2$-approximation is known for PVC. To ...

1

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|$. Let $\mathcal U\subseteq [0,1]$ be a set of Lebesgue measure 0. (For instance, $\mathcal U$ could be the set of all numbers whose binary expansion does not ...

1

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 bitstrings of the form $a_1a_2\ldots a_n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$. Two vertices $a_1a_2 \ldots a_n$ and $b_1b_2\ldots b_n$ are ...

1

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(86)90174-X, section 5.

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