# 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 Commented Apr 6, 2017 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". Commented Apr 6, 2017 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). Commented Apr 6, 2017 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. Commented Apr 7, 2017 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. Commented Apr 7, 2017 at 13:18