The apx tag has no wiki summary.
6
votes
4answers
302 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
332 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 ...
