Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
33 views

Which problems are (or could be) APX-Hard without being in APX (i.e. problems with no poly-time algorithm with fixed multiplicative error)?

APX problems are those optimization problems in NP which admit a polynomial time algorithm which achieves a fixed multiplicative approximation to the optimal value. APX-Hard problems are those ...
Another User's user avatar
3 votes
1 answer
88 views

Deciding if max-cut with negative edge weights has a solution with positive value

I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value: Given a graph $G=(V, E)$ and edge weights $w: E \...
badboul's user avatar
  • 77
1 vote
0 answers
46 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 ...
John's user avatar
  • 412
3 votes
0 answers
51 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 ...
John's user avatar
  • 412
0 votes
1 answer
108 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 ...
John's user avatar
  • 412
3 votes
0 answers
72 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 ...
MatroMan's user avatar
2 votes
0 answers
37 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 ...
John's user avatar
  • 412
2 votes
1 answer
79 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. ...
John's user avatar
  • 412
3 votes
0 answers
100 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 ...
John's user avatar
  • 412
1 vote
1 answer
105 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 ...
Michael C.'s user avatar
0 votes
0 answers
35 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 ...
Anand Subramani's user avatar
3 votes
0 answers
84 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 ...
a3nm's user avatar
  • 9,449
1 vote
0 answers
105 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 ...
user135520's user avatar
0 votes
0 answers
50 views

Why are impossibility results harder for uniform sparsest cut than non-uniform?

My question is this: why is it the case that the uniform cost version of the Sparsest Cut problem has eluded hardness of approximation results whereas the non-uniform version has not; my intuition is ...
Dowdow's user avatar
  • 9
0 votes
0 answers
90 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 ...
John's user avatar
  • 412
1 vote
1 answer
187 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 ...
John's user avatar
  • 412
3 votes
1 answer
222 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 ...
John's user avatar
  • 412
2 votes
0 answers
58 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 ...
John's user avatar
  • 412
1 vote
0 answers
61 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 ...
Nithish kumar's user avatar
1 vote
1 answer
155 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 ...
Bell's user avatar
  • 53
1 vote
0 answers
123 views

Is finding a very large clique NP-hard?

We know that, unless P=NP, for any $\epsilon$ we can't distinguish in polynomial time between the two cases: There exists a clique of size at least $n^{1-\epsilon}$ All cliques have size at most $n^\...
Dmitry's user avatar
  • 201
5 votes
1 answer
215 views

Hashing-based vs almost uniform sampling-based approximate counting

Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states: For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
delete000's user avatar
  • 828
4 votes
0 answers
103 views

Analogue of Chow-Liu tree for $L_1$

Say $\Omega$ is a finite set and $f$ a probability mass function (pmf) over $\Omega^d$. Now let $T$ be a spanning tree on the set $V=\{1,2,\ldots,d\}$, and consider a collection of one- and two- ...
Aryeh's user avatar
  • 10.6k
0 votes
0 answers
99 views

Large CLIQUE approximation

I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices. ...
Bolton Bailey's user avatar
5 votes
0 answers
242 views

$\#$P hardness of computing weighted sum of degree $2$ polynomials

Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...
AngryLion's user avatar
  • 173
0 votes
1 answer
63 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 ...
Mohemnist's user avatar
  • 230
2 votes
1 answer
138 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 ...
user avatar
3 votes
0 answers
155 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) ...
Root's user avatar
  • 387
3 votes
0 answers
166 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 (...
Inuyasha Yagami's user avatar
3 votes
1 answer
143 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 ...
Tassle's user avatar
  • 881
4 votes
0 answers
341 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 \begin{equation} \left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
AngryLion's user avatar
  • 173
2 votes
0 answers
104 views

Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\...
Lamine's user avatar
  • 1,137
6 votes
1 answer
293 views

Why does Dinur's proof of the PCP theorem fail to work for unique games?

What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
user's user avatar
  • 61
1 vote
1 answer
85 views

Best approximations of Minimum Dominating Sets in chordal graphs

I am searching results and papers related to the (in)approximability of the Minimum Dominating Set problem in chordal graphs. In particular, what is the best approximation ratio achievable in polytime ...
Mathieu Mari's user avatar
1 vote
0 answers
57 views

polytime approximability of directed multicut

Does anyone know how well directed multicut can be approximated in planar and minor free graphs? Also any survey of approximability of directed multicut and multicut in various graph classes would be ...
user122938's user avatar
1 vote
2 answers
109 views

Where to find info on (polytime) approximability of various discrete optimization problems?

Where to find info on (polytime) approximability of various discrete optimization problems? Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of ...
user122938's user avatar
6 votes
1 answer
307 views

Good Survey paper for k-means/k-median/k-center/facility-location

I have stated 4 problems in the Question title. All these problems are closely related and are studied in various variations. For example: Space: Euclidean/metric/discrete/continuous/non-metric/2-...
Inuyasha Yagami's user avatar
10 votes
1 answer
617 views

Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
maxdan94's user avatar
  • 563
0 votes
0 answers
42 views

Different version of approximation complexity and algorithm for densest-k-subgraph problem

In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
Laoxuexian's user avatar
-1 votes
1 answer
113 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 ...
G Oliveira's user avatar
0 votes
1 answer
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 ...
Cyriac Antony's user avatar
2 votes
0 answers
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 ...
Nikita Lukyanenko's user avatar
1 vote
1 answer
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 ...
Cyriac Antony's user avatar
0 votes
1 answer
189 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)$ ...
Cyriac Antony's user avatar
-1 votes
1 answer
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 ...
Mathieu Mari's user avatar
2 votes
0 answers
109 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 ...
Bartolinio's user avatar
1 vote
0 answers
74 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 [...
xyguo's user avatar
  • 191
2 votes
0 answers
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 ...
domotorp's user avatar
  • 14k
3 votes
0 answers
83 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 ...
Elliot Gorokhovsky's user avatar
5 votes
0 answers
76 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 ...
Abel Molina's user avatar
  • 1,424

1
2 3 4 5