# Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

200 questions
Filter by
Sorted by
Tagged with
84 views

• 122
1 vote
73 views

### Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?

In the maximum coverage problem (also known as max k-cover) we are given a universe $U = \{e_1,\ldots, e_n\}$ of elements, a collection $F = \{S_1,\ldots, S_m\} \subseteq 2^U$ of sets over $U$, and an ...
• 412
56 views

### Partial Hamiltonian Path Optimization Problem

Let $G = (V,E)$ be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in $G$ of maximum cardinality, such that (i) the in-degree and out-degree of each ...
• 412
123 views

### Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

The paper [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Austrin, Khot, Safra] Shows that assuming the Unique Game Conjecture (UGC) the minimum vertex cover problem ...
• 412
83 views

### Hardness of Approximation for Three Matroid Intersection

I am searching for the best known hardness of approximation bound for three matroid intersection. The input is three matroids on the same ground set which are accessible using three different ...
• 31
42 views

### Hardness of Coloring based on a Black-Box Hardness of Independent Set

It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent ...
• 412
97 views

### Set Cover with Multiple covers

I am interested in whether a set cover instance that covers all elements $q$ times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. ...
• 412
108 views

### maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
• 412
1 vote
127 views

### A variant of the generalised assignment problem

I am trying to solve this problem: There are $N$ workers and $T$ tasks. Each task can be assigned to at most one worker. Each worker can be assigned any number of tasks. The profit obtained by ...
45 views

### Is Maximum monotone NAE3SAT APX-hard?

I know that monotone NAE3SAT is NP-complete. I also know that MAXNAE3SAT is APX-complete. Note that I am using a monotone formula to mean with with no negated literals anywhere. Anyway, my question is ...
89 views

### FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge ...
• 9,697
1 vote
107 views

### If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?

I'm trying to understand the statement in the introduction (pg 1) of this work by Anari et all on approximating the permanent $\text{per}(A)$ of a positive semi-definite matrix $A$. The statement, I'm ...
• 111
93 views

### When Exponential Costs are Essential for NP-Hardness?

In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
• 412
1 vote
196 views

### 3 Matroid Intersection, a Special Case

It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard. Question: Does this problem remain NP-Hard if one of the matroids ...
• 412
286 views

### Hardness of Maximum Independent Set in 3-Colorable Graphs

Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors. Question: In such graphs, are there known results for the hardness of finding a ...
• 412
60 views

### Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?

In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph $G = (L,R,E), |L| = |R| = n$ and the goal is to find an induced subgraph of $G$, $G' = (L',R',E')$, with as ...
• 412
1 vote
66 views

### Reduction from unweighted graphs to weighted graphs?

Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around). My objective is to do something similar to the following: If the ...
1 vote
181 views

### Approximation algorithm for balanced bipartite independent set?

The Problem: Given a bipartite graph $G = (L,R,E)$ with $|L|=|R|=n$, the balanced bipartite independent set problem asks us to output the largest vertex subsets $A\subseteq L, B\subseteq R$ of equal ...
• 53
1 vote
123 views

• 193
64 views

### Set cover where consecutive sets differ by at most one item [closed]

First I define my version of the set cover problem: We have a collection of sets such as $S_1, \dots, S_m$ where each $S_i$ is a subset of $M=\{1,\dots, m\}$. The goal is to find the minimum number of ...
• 240
140 views

### Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
157 views

### Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
• 387
169 views

### Incorrect Lower Bound of k-Means++ Algorithm

The $k$-means++ algorithm is composed of two parts: Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling. Expectation maximization part: the standard $k$-means algorithm (...
• 1,541
151 views

### Approximating Independent Dominating set on bipartite graphs

I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices. My question is: are there any positive results in the ...
• 881
371 views

### Improving the approximation in Stockmeyer's counting theorem

Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
• 193
106 views

116 views

### Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
• 103
99 views

### Optimization problems with same optimal value, but different approximation behavior

Context: related to this answer. I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense ...
• 1,827
105 views

### Complexity of a scheduling problem with a fixed left bound of jobs

Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
1 vote
244 views

### Hardness of approximating acyclic chromatic number

I have some doubts on the inapproximability result for acyclic coloring presented in the paper New acyclic and star coloring algorithms with application to computing Hessians. They claim that there ...
• 1,827
194 views

### Problems that are NP-hard to approximate even when the input graph is regular

Are there graph problems which are NP-hard to approximate even when the input graph is regular? For instance, are there optimization problems that are NP-hard to approximate within $O(n^\epsilon)$ ...
• 1,827
78 views

### the shorstest cycle containing two given points

I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
• 475
120 views

### How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
• 203
1 vote
75 views

### Sherali-Adams lowerbound instance of Unique Games constructed via CLT

The question comes from the following paper I have been reading: [1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev. Theorem 6.1 of [...
• 191
111 views

### How hard is it to determine ex(n,G)?

Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
• 14.1k
85 views

### Example of a hardness-of-approximation proof which improves the approximation factor?

Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...
80 views

### Hard family for degree-$D$ MAX-3LIN

Max 3LIN is the problem where one is given a linear system of equations $C$ over $\mathbb{F}_2$ with $3$ variables per equation, and needs to determine the maximum number of equations that can be ...
• 1,424
I am considering the following problem. Input: Given two disjoint subsets $A$ and $B$ and a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq A \cup B$ for all $i=1\ldots k$. ...