Hardness of approximation, aka inapproximability.
1
vote
1answer
55 views
number of PCP queries
we know from the PCP theorem that $PCP[O(log(n)),O(1)]=NP$,what if we choose specific number of queries will the theorem hold ?
-4
votes
0answers
40 views
What do these Codes mean? [closed]
Code 1-
public void actionPerformed(ActionEvent e) {
if (inGame) {
checkApple();
checkCollision();
move();
}
repaint();
}
--------------------------------------…
Code 2-
public void ...
9
votes
0answers
127 views
Smoothed analysis of approximation algorithms
Smoothed analysis has been applied many times to understand the runtime of exact algorithms for many problems like linear programming and k-means. There are fairly general results in this realm, for ...
5
votes
4answers
407 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 ...
0
votes
0answers
96 views
proving $P \subseteq PCP(0,O(log(n))$ [closed]
I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to ...
6
votes
0answers
143 views
Hitting sets with a subfamily
Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects.
A family $H$ of $k$-element subsets of $U$, with $1 \le k < d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ ...
5
votes
0answers
79 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}
...
7
votes
0answers
141 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 ...
12
votes
4answers
492 views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
4
votes
0answers
108 views
Hardness of approximating |V|+(size of vertex cover)
I know that UGC implies a hardness of 2 for vertex cover, but is there a way to have this hardness on instances where the size of the vertex cover is at least $(1-\epsilon)\frac{|V|}2$? More generally ...
6
votes
2answers
180 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?
27
votes
4answers
1k views
Hardness of approximation without the PCP theorem
An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any ...
3
votes
2answers
158 views
What is the best-known inapproximability result for MIN-3CNF-DELETION?
I am really curious what the best-known inapproximability result is for MIN-3CNF-DELETION. To clarify, this is the problem of minimizing the number of unsatisfied clauses in a CNF
SAT formula with at ...
10
votes
2answers
194 views
Approximability of the genus problem
What is currently known about the approximability of the genus problem? A preliminary search tells me that a constant factor approximation is trivial for sufficiently dense graphs, and an ...
-5
votes
1answer
177 views
Is 3SAT problem APX-hard or not?
Could you point me a reference, an answer or it is an open question?
-3
votes
1answer
229 views
What is meant by “if there exists a $\rho$-approximation algorithm with $\rho < 2$, then P = NP”?
For example, for the $k$-center problem we want to prove that a 2-approximation algorithm is optimal.
A proof is presented on page 39 (Theorem 2.4) in Williamson and Shmoys, The Design of ...
20
votes
1answer
414 views
What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?
There are many inapproximability results which rely on the unique games conjecture. For example,
Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within ...
4
votes
1answer
167 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 = ...
8
votes
0answers
96 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 ...
4
votes
1answer
206 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 ...
4
votes
0answers
275 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 ...
5
votes
1answer
442 views
What are good approximation algorithms for the subset sum problem so far?
By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
8
votes
1answer
192 views
Request for references on multicommodity flow-cut results
This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...
10
votes
0answers
143 views
Inapproximability of multiterminal cut
In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
5
votes
0answers
232 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 ...
3
votes
2answers
118 views
Approximation results on scheduling under an uncommon constraint
I am looking for any approximation results for unrelated multiprocessor scheduling problem with precedence constraints (minimizing makespan), i.e. $R|prec|C_{max}$, with the constraint that some tasks ...
11
votes
0answers
202 views
Approximating and bounding Ramsey numbers
Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer:
Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and ...
5
votes
0answers
193 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 ...
12
votes
2answers
280 views
Hierarchy theorem for approximation ratios?
As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have ...
10
votes
1answer
229 views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
4
votes
0answers
159 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 ...
8
votes
1answer
352 views
Is Max-Cut APX-complete on triangle-free graphs?
In the Max-Cut problem, one seeks a subset S of vertices of a given simple undirected graph such that the number of edges between S and the complement of S is as large as possible.
Max-Cut is ...
8
votes
1answer
383 views
Inapproximability of set cover: can I assume m=poly(n)?
I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem ...
2
votes
1answer
125 views
hardness of approximation result for a Min-CSP, by reduction from PCPs
Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for ...
0
votes
0answers
214 views
Hardness of min-max problems
Consider the following min-max problem
Given a graph $G=(V,E)$ and an integer $k \geq 0$, delete at most $k$ nodes in $G$ to maximize the size of the minimum dominating set in the residual graph.
...
4
votes
1answer
227 views
Approximating Random MAX-k-SAT
It is known [de la Vega & Karpinski 2002] that random instances of MAX-3-SAT on $n$ variables can be approximated up to fraction at least 8/9 w.h.p. tending to 1 as $n$ tends to infinity.
Should ...
7
votes
0answers
151 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 ...
2
votes
1answer
219 views
Connectivity Problem
Hi. I have a problem but not sure if there is some literature on it or whether it has a standard name. Please let me know some reference from where I can begin.
Given undirected graph along with some ...
9
votes
2answers
299 views
Maximizing sum edge weights
I am wondering if the following problem has a name, or any results related to it.
Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all ...
6
votes
2answers
232 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 ...
2
votes
1answer
210 views
Explain 0-extension algorithm
I'm trying to implement an approximation algorithm for the 0-extension problem
I found the following paper:
Approximation Algorithms for the
0-extension problem by Gruia
Calinescu, Howard ...
14
votes
1answer
239 views
Hitting set of pairwise intersecting families
A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$.
The problem to find a minimum hitting ...
9
votes
2answers
312 views
Existence of $opt^c$-approximation of Dominating Set with $c < 1$?
Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. ...
35
votes
3answers
2k views
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect ...
22
votes
4answers
687 views
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a ...
16
votes
3answers
356 views
Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?
There is a standard approximation theory where the approximation ratio is $\sup\frac{A}{OPT}$ (for problems with $MIN$ objectives), $A$ - the value returned by some algorithm $A$ and $OPT$ - an ...
0
votes
0answers
262 views
best approximation ratio for the max-clique problem
Which one is the best approximation algorithm for the max-clique problem? What is it's approximation ratio?
7
votes
1answer
424 views
Is MAX CUT approximation resistant?
CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since a random ...
11
votes
2answers
218 views
Which 2P1R Games are Potentially Sharp?
Two-prover one-round (2P1R) games are an essential tool for hardness of approximation. Specifically, the parallel repetition of two-prover one-round games gives a way to increase the size of a gap in ...
6
votes
4answers
303 views
In-approximability results in severely restricted graph classes
Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$). I don't know if it remains in-approximable in cubic bipartite ...
