Questions tagged [approximation-hardness]
Hardness of approximation, aka inapproximability.
191
questions
0
votes
0
answers
29
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 ...
3
votes
0
answers
70
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 ...
- 8,896
1
vote
0
answers
99
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
0
votes
0
answers
39
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 ...
- 9
0
votes
0
answers
88
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 ...
- 173
1
vote
1
answer
159
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 ...
- 173
3
votes
1
answer
152
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 ...
- 173
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 ...
- 173
1
vote
0
answers
52
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
1
answer
130
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
0
answers
120
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^\...
- 201
5
votes
1
answer
192
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 ...
- 778
4
votes
0
answers
101
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- ...
- 10.3k
0
votes
0
answers
92
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.
...
- 131
5
votes
0
answers
240
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 $\...
- 173
0
votes
1
answer
62
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 ...
- 230
2
votes
1
answer
136
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 ...
user53330
3
votes
0
answers
154
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
3
votes
0
answers
158
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,531
3
votes
1
answer
137
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 ...
- 691
4
votes
0
answers
273
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(...
- 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}\...
- 1,137
6
votes
1
answer
285
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 ...
- 61
1
vote
1
answer
79
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 ...
- 475
1
vote
0
answers
54
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 ...
- 21
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 ...
- 21
6
votes
1
answer
296
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-...
- 1,531
10
votes
1
answer
610
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 ...
- 563
0
votes
0
answers
40
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[...
-1
votes
1
answer
95
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
0
votes
1
answer
98
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,723
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 ...
1
vote
1
answer
243
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,723
0
votes
1
answer
183
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,723
-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 ...
- 475
2
votes
0
answers
98
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
0
answers
70
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
2
votes
0
answers
107
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 ...
- 13.9k
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 ...
5
votes
0
answers
75
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
3
votes
1
answer
256
views
Maximum Positive Negative Set Cover Problem
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$.
...
- 107
3
votes
0
answers
76
views
Hardness of Approximation of Set Cover with Growing Size Bound
I'm considering the minimum set cover problem with the constraint that each set contains at most $k$ elements.
Here, $k$ depends on the size of the universe.
For example, $k$ may equal $\log n,\sqrt ...
- 101
6
votes
1
answer
81
views
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:
There is a value $\...
- 1,424
5
votes
0
answers
202
views
Is monotone 1-in-3 MAXSAT known to be APX hard?
Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
- 1,177
3
votes
0
answers
96
views
Is #PP2DNF hard to approximate?
The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the ...
- 165
3
votes
2
answers
195
views
Minimum relevant variables in linear system - additive approximation
In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.:
$$ A x = b $$
and the goal is to find a solution $x$ with as few nonzero variables as ...
- 2,078
2
votes
0
answers
172
views
Best polynomial-time approximation factor for NP-optimization problems
Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold:
There exist a polynomial-time algorithm $A,$ and an integer $n_0$, ...
- 11.3k
3
votes
1
answer
64
views
Distinguising between the cases of low or high cover number
Is there a known result saying that for some constants $0 < a < b < 1$, it is NP-hard to distinguish a graph having vertex cover number at most $a \cdot n$ from a graph having vertex cover ...
7
votes
1
answer
336
views
Does Max Planar 3-SAT admit a PTAS?
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
- 475
1
vote
0
answers
67
views
Reasoning about NP hardness of optimization problems with closed form functions as input
(This may not be a research level question per se. I can delete this question if the community thinks this way too)
I am trying to understand how to reason about hardness of optimization problems ...
- 1,177