Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

Filter by
Sorted by
Tagged with
3
votes
1answer
84 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 ...
3
votes
0answers
71 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(...
2
votes
0answers
73 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
vote
0answers
76 views

Hardness of Approximation of Continuous Metric k-Median

First let me describe the metric $k$-median problem. Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...
0
votes
0answers
46 views

Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be ...
6
votes
1answer
206 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 ...
1
vote
0answers
145 views

What does it mean by the statement: “a problem is hard to approximate ”?

In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&...
1
vote
1answer
41 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 ...
1
vote
0answers
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 ...
0
votes
0answers
75 views

Hardness of approximation by reduction from MAX-E3SAT

For the MAX-E3SAT define $k=\sum_i^n (g_i-1)$, where $n$ is the number of variables and $g_i=\text{max}(\{\text{occurrences of }x_i, \text{occurrences of }\neg x_i\}), \text{ for each }i=\{1,\ldots,n\}...
1
vote
2answers
105 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 ...
6
votes
1answer
177 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-...
9
votes
1answer
489 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 ...
0
votes
0answers
33 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
1answer
61 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 ...
0
votes
1answer
84 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 ...
2
votes
0answers
100 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
1answer
213 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 ...
0
votes
1answer
141 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
votes
1answer
72 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 ...
2
votes
0answers
77 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 ...
1
vote
0answers
52 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 [...
2
votes
0answers
92 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 ...
3
votes
0answers
77 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
0answers
52 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 ...
2
votes
1answer
187 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$. ...
3
votes
0answers
59 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 ...
6
votes
1answer
73 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 $\...
5
votes
0answers
119 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 ...
3
votes
0answers
78 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 ...
3
votes
2answers
146 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
votes
0answers
162 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$, ...
3
votes
1answer
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
1answer
233 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 ...
1
vote
0answers
61 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 ...
5
votes
0answers
54 views

Inapproximability Results for APX-hard Geometric Optimization Problems

A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to ...
9
votes
0answers
198 views

Which version of KAKUTANI does lie in PPAD?

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
0
votes
1answer
174 views

Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph. Input: Given a graph G with non-negative vertex weights and valid ...
3
votes
0answers
336 views

Hardness of Approximation for minimum path cover in an undirected graph?

Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
3
votes
0answers
44 views

Approximating a monotone submodular function using a concrete coverage function

Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e. Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to ...
1
vote
1answer
599 views

Approximately counting paths and cycles in a graph

Counting cycles, and paths in graphs is a hard problem, see questions here, and related question for cycles for a given length $k$, here. The question is about the approximability of these graph ...
1
vote
0answers
103 views

Does the NP-hardness of finding any valid solution imply NPO-hardness?

Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as ...
3
votes
0answers
128 views

Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i? $" for some $i$, taking the left branch means "yes", ...
6
votes
0answers
158 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
2
votes
1answer
397 views

Is there any known Poly-APX-complete minimimization problem?

All Poly-APX-complete problems I know are maximization problems, e.g. Max Clique, Max Independent Set, Max One for some set of contraints, and even choosing the attributes of a product to maximize (...
1
vote
2answers
310 views

Is Asymptotic PTAS $\subseteq$ APX?

The definition of asymptotic polynomial-time approximation scheme (Asymptotic PTAS) is defined as follows: A minimization problem $\Pi$ is Asymptotic PTAS if for all $\epsilon$ there exists an ...
2
votes
0answers
66 views

On the impossibility of representing/approximating subadditive function using additive functions

I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \...
1
vote
1answer
115 views

hardness of constant approximation of largest matching set

We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more. Given a graph $G=(V,E)$ a subset $U\subseteq V$...
2
votes
0answers
177 views

Approximating the Radius of a (Dense) Graph

For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
2
votes
0answers
59 views

Studying the hardness of polynomial-time approximability using the concept of stability of approximation

In the Conclusion section, the author of this paper "Stability of Approximation Algorithms for Hard Optimization Problems" by Juraj Hromkovič, 1999 claims that Using the notion of stability one can ...