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


11

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

No need to approximate, we can determine the exact value: see Kőnig's theorem. In particular, this section shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover.


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

Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq ...


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

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.


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


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

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


3

Yes, this is closely related to the Domatic Partition problem. See the paper below. http://epubs.siam.org/doi/abs/10.1137/S0097539700380754 One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set ...


3

This is a special case of what is called an $f$-c.e. set. A set $A$ is $f$-c.e. iff there is computable function $g$ such that $\chi_A(x) = \lim_i g(x,i)$, and $\forall x \ |\{s \mid g(x,i) \neq g(x,i+1) \}| \leq f(x)$. If we consider $f(x)=n$ then we get the definition of $n$-c.e sets. They don't need to be c.e. because c.e. is not closed under ...


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

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