# Questions tagged [approximation-hardness]

Hardness of approximation, aka inapproximability.

200 questions
Filter by
Sorted by
Tagged with
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 ...
• 14.5k
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 ...
• 2,153
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 ...
• 16.5k
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?
• 149
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'...
• 1,166
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$, ...
• 13k
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 ...
• 475
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://...
• 1,453
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). ...
• 2,153
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 ...
• 2,281
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 ...
• 951
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 ...
• 71
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 ...
• 4,479
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 ...
• 343
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 ...
• 2,044
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 ...
• 163
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 ...
• 1,142
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 ...
• 51.1k
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 ...
• 61
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 ...
• 575
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-...
• 1,531
84 views

• 173
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 ...
• 1,424
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 ...
• 1,177
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 ...
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 ...
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 ...
• 958
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}$...
• 1,224
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 ...
• 1,453
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 \sum_{k=...
• 1,036
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$...
• 456
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-...
• 165
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, ...
• 91
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?
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 ...
• 7,615
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 ...
• 163