Skip to main content

Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

Filter by
Sorted by
Tagged with
8 votes
0 answers
232 views

NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
Yuval Filmus's user avatar
  • 14.5k
8 votes
0 answers
178 views

Is the dominating set problem constant-factor-approximable in undirected path graphs?

I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class. A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
Florent Foucaud's user avatar
8 votes
0 answers
1k views

Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?

This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware. Informal ...
Tsuyoshi Ito's user avatar
  • 16.5k
7 votes
2 answers
352 views

Inappoximability status of Max One in Three SAT for satisfiable instances

What is the inapproximability status of Max-One-in-Three SAT for satisfiable instances?
vikku's user avatar
  • 149
7 votes
4 answers
2k views

Hardest problems to approximate

Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'...
Austin Buchanan's user avatar
7 votes
1 answer
702 views

Permanents - Approximation and connection to integer factorization

Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, ...
Turbo's user avatar
  • 13k
7 votes
1 answer
362 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 ...
Mathieu Mari's user avatar
7 votes
1 answer
229 views

What are the hardness results known for CSP over $\mathbb{F}_q$?

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...
gradstudent's user avatar
  • 1,453
7 votes
1 answer
458 views

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3). ...
Florent Foucaud's user avatar
7 votes
0 answers
348 views

Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of ...
argentpepper's user avatar
  • 2,281
7 votes
0 answers
851 views

Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
aelguindy's user avatar
  • 951
7 votes
0 answers
701 views

Hardness of Approximation results for Special Set Packing Problem Wanted

Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem? The general Set Packing Problem would be: Given A Collection of ...
Neele's user avatar
  • 71
7 votes
0 answers
545 views

Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?

optimization problem Input: a 3-connected cubic planar graph feasible solution: A simple path measure to optimize: length of the simple path Is there a constant approximation algorithm for this ...
Chao Xu's user avatar
  • 4,479
7 votes
0 answers
271 views

Results regarding Bounded Diameter Minimum Spanning Tree

Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of ...
user5153's user avatar
  • 343
6 votes
4 answers
805 views

How to start studying topics Hardness of approximation and PCP's

Recently I have done an introductory course on complexity theory ( which covered 90% of sipser text book). Now I would like to study the topics Hardness of approximation and PCP's. Can you please ...
Kumar's user avatar
  • 2,044
6 votes
2 answers
438 views

Hardness of additive approximation to Graph Coloring problem.

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the ...
Buss's user avatar
  • 163
6 votes
3 answers
454 views

Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

Problem: Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that ...
Phylliida's user avatar
  • 1,142
6 votes
1 answer
348 views

Complexity of finding large grid minors

What is the complexity of finding the largest $k\times k$ grid graph that is a minor of a given graph $G$? It is FPT in $k$, and it seems likely to be NP-hard (or NP-complete in a decision version ...
David Eppstein's user avatar
6 votes
1 answer
295 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
6 votes
2 answers
690 views

Variants of Densest Subgraph Problems

Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$: (1) Average degree of vertices in $H$ (2) What I will ...
sd234's user avatar
  • 575
6 votes
1 answer
308 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
6 votes
1 answer
84 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 $\...
Abel Molina's user avatar
  • 1,424
6 votes
1 answer
1k views

Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for ...
Yury Kartynnik's user avatar
6 votes
0 answers
193 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 $$\...
Paul's user avatar
  • 271
6 votes
0 answers
363 views

Approximating the diameter of a convex set defined by semidefinite constraints

A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations. Now, if you want to minimize a linear ...
Vincent Nesme's user avatar
6 votes
1 answer
247 views

Hardness of approximating chromatic number of triangle-free graphs

The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs. Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
Peng Zhang's user avatar
  • 1,453
5 votes
1 answer
325 views

Set cover in which some pairs of sets are forbidden

I'm trying to find an approximation algorithm for a variant of the weighted set cover problem. However, this variation doesn't seem to let me apply the traditional set cover arguments for an ...
Manuel Lafond's user avatar
5 votes
1 answer
217 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
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
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
5 votes
0 answers
242 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 ...
karmanaut's user avatar
  • 1,177
5 votes
0 answers
72 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 ...
user avatar
5 votes
0 answers
247 views

Maximizing the number of selected edges with opposing requirements

Consider the following problem: Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$. Output: a subset of vertices $W$ of size $k$ which maximizes the ...
Vadapalli Adithya's user avatar
5 votes
0 answers
258 views

Is MAX-SAT SETH (like) hard?

If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy. There ...
Thomas Ahle's user avatar
5 votes
0 answers
121 views

The distribution on the solution space induced by randomized rounding

Consider the Goemans-Williamson algorithm for the MAX-CUT problem. It is known, that if $maxcut(G) \geq 1-\epsilon$, then the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$...
Lior Eldar's user avatar
  • 1,224
5 votes
0 answers
389 views

Approximate c-chromatic number, each color class is P4-free (cograph)

The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
Peng Zhang's user avatar
  • 1,453
5 votes
0 answers
147 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\\{1,\ldots,m\\}$, I want to maximize the quantity \begin{equation} \sum_{k=...
Thomas Kalinowski's user avatar
4 votes
1 answer
302 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$...
TCSGrad's user avatar
  • 456
4 votes
1 answer
326 views

Complexity of linear programming

It is known that Linear Programming (LP) is P-complete. I am interested in approximation algorithms for LP. There are numerous inapproximability results for NP optimization problems, e.g. it is NP-...
user0928's user avatar
  • 165
4 votes
2 answers
699 views

Graph coloring/partitioning problem

I'm interested in the complexity of the following problem: Problem $P$: Given an undirected planar graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{Z}$ (so weights can be negative, ...
eakbas's user avatar
  • 91
4 votes
1 answer
89 views

Bellman principle and approximability

Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
Bruglieri's user avatar
4 votes
1 answer
2k views

Maximizing a monotone supermodular function s.t. cardinality

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this. Question: Is it known to be true or is there a hardness result ...
usul's user avatar
  • 7,615
4 votes
1 answer
88 views

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
Mark's user avatar
  • 163
4 votes
1 answer
223 views

Algorithms for Interval Coloring with Capacities and Demands

We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = [s_i,...
Arindam Pal's user avatar
  • 1,591
4 votes
1 answer
195 views

Approximation algorithms for multicut for special classes of graphs

The multicut problem is the following. Given a graph $G=(V,E)$ with edge costs $c_e$ for edge $e$ and a set of $k$ terminal pairs $\{(s_1,t_1),\ldots,(s_k,t_k)\}$, the objective is to find a set of ...
Arindam Pal's user avatar
  • 1,591
4 votes
1 answer
116 views

From Lasserre maps to pseudo-distributions

Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is ...
gradstudent's user avatar
  • 1,453
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
4 votes
0 answers
344 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
4 votes
0 answers
588 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 ...
Bell's user avatar
  • 53
4 votes
0 answers
173 views

Set cover approximation ratio as a function of m (number of sets)

Feige's well known result (and more recent results) show that set cover cannot be approximated within a factor of $(1 - o(1)) \ln n$, where $n$ is the number of variables. What if we want an ...
David Harris's user avatar
  • 3,508