Questions tagged [apx]
The apx tag has no usage guidance.
8
questions
16
votes
2
answers
2k
views
Is APX contained in NP?
A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c.
APX contains PTAS (seen by ...
- 398
16
votes
0
answers
489
views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
- 6,470
8
votes
4
answers
410
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$ unless $P=NP$). I don't know if it remains in-approximable in ...
- 20.9k
8
votes
1
answer
539
views
Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?
Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
- 103
5
votes
1
answer
323
views
Best approximation for a HYPERGRAPH-MAXDICUT problem
Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
3
votes
1
answer
366
views
On APX problems
Given optimization problems $P1$ and $P2$. The slides below say that, $P1 \leq_L P2$ does not imply $P2 ∈ APX$, then $P1 ∈ APX$. Why is this so?
http://www.di.univr.it/documenti/AttDidAva/allegato/...
- 12.9k
0
votes
1
answer
556
views
PAC algorithms for APX-Hard problems
Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every $\...
- 161
0
votes
0
answers
112
views
How can I show that zero-one programming is not in APX?
How can I show that zero-one programming is not in APX?
Vertex Cover Problem is in the APX class. So can I try a PTAS-reduction from the
zero-one programming problem to Vertex Cover and show that ...
