The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
45 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 ...
0
votes
1answer
102 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 ...
5
votes
1answer
140 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
1answer
205 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? ...
7
votes
4answers
340 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 ...
13
votes
2answers
365 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 ...