# Looking for approximation class between NPO and Exp-APX

I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) is trivial, although obtaining solutions with any quality higher than 0 is NP-hard.

If I get it right, problem A cannot be in Exp-APX: any polynomial-time algorithm would return solutions with 0 quality, so the performance ratio (i.e. quality of best solution / quality of found solution) of any polynomial-time algorithm would be infinite in the worst case. Thus the performance ratio cannot be exponentially bounded.

On the other hand, finding some bad solution for problem A is trivial, which is not the case of NPO-complete problems such as e.g. MAX {0,1}-LINEAR PROGRAMMING or MAX WEIGHTED 3-SATISFIABILITY, where finding any valid solution is NP-hard. Therefore, problem A cannot be NPO-hard, right? In particular, an AP-reduction couldn't map 0-valued solutions of problem A into some solutions of MAX {0,1}-LINEAR PROGRAMMING, as finding any solution to the latter problem is NP-hard.

So, is there any known approximation class X such that problem A could be X-hard?

Related question 1: What version of TSP is said to be Exp-APX-complete? Is it "all pairs of nodes are connected" + "the minimal distance between nodes is 1"? If finding some hamiltonian cycle weren't easy, or if 0-length round trips could exist, then the problem couldn't be in Exp-APX, could it?

Related question 2: Is there any "Max TSP" variant (i.e. finding longest round trips) that is Exp-APX-complete? Or any other Exp-APX-complete problem (preferably a maximization one) I could use to prove the Exp-APX-hardness of A?

• Related question 1: Yes, you must avoid solutions of objective value 0. Related question 2: As long as you insist on non-negative distances between cities, the corresponding MaxTSP will be contained in APX. See for instance Fisher, Nemhauser, Wolsey "An analysis of approximation for finding a maximum weight Hamiltonian circuit" Operations Research 27 (1979) 799-809 – Gamow Apr 6 '17 at 11:47
• About RQ1: For containment in Exp-APX, you need to avoid an objective value 0. (However, the special case where at most $n-1$ of the distances are 0, would still be contained in Exp-APX.) I do not see why you would need all pairs to be connected. But perhaps you should first specify precisely what you mean by the word "requires". – Gamow Apr 6 '17 at 11:58
• About RQ2: Yes, the general MaxTSP with non-negative distances between cities is in APX. Fisher, Nemhauser, Wolsey give a 1/2 approximation algorithm for it; nowadays better approximation ratios are known (-> google). – Gamow Apr 6 '17 at 12:00
• Can't you turn any NPO-complete problem into a EXP-APX complete one by adding a dummy solution whose weight is as small or as large as possible. – Markus Bläser Apr 7 '17 at 8:19
• At least in the definition of NPO given in the book by Aussiello et al, Complexity and Approximation, Springer, 1999, every feasible solution needs to have a positive objective value. – Markus Bläser Apr 7 '17 at 13:18