<p>As pointed out by Markus Bläser in the comments section, objective values must be positive integers, so they cannot be 0. Hence my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". In fact, under that new definition, problem A turns out to be NPO-complete.</p>

CC BY-SA 3.0
2017-04-25T08:36:17.520Z
2017-04-25T08:36:17.520Z
EXPTIME-complete
<p>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.</p>

<p>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. </p>

<p>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.</p>

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

<p>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? </p>

<p>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?</p>

CC BY-SA 3.0
2017-04-06T11:47:44.167Z
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
CC BY-SA 3.0
2017-04-06T11:51:28.757Z
RQ1: So the version of TSP which is Exp-APX-complete requires all pairs to be connected and edge costs be at least 1, this is what I supposed, thank you. RQ2: Is it in APX even if graphs are general (i.e. no metric or geometric constraint)?
EXPTIME-complete
CC BY-SA 3.0
2017-04-06T11:58:10.213Z
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
CC BY-SA 3.0
2017-04-06T12:00:29.630Z
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
CC BY-SA 3.0
2017-04-06T12:05:02.173Z
About RQ1: You are right, the connectiviy of all pairs is a sufficient but not necessary condition. We need graphs where we can find at least one Hamiltonian cycle in polynomial time (otherwise no polynomial-time approximation could always find some solution). This happens indeed if all pairs of nodes are connected, but it is not necessary.
EXPTIME-complete
CC BY-SA 3.0
2017-04-06T12:17:50.490Z
About RQ2: Thanks for the info. So in order to prove the Exp-APX-hardness of my problem A, now I know I cannot e.g. AP-reduce Max TSP into A. It's a pity, as reductions where both problems are max or both problems are min are typically more intuitive, but I don't know any Exp-APX-complete maximization problem.
EXPTIME-complete
CC BY-SA 3.0
2017-04-07T08:19:38.637Z
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
CC BY-SA 3.0
2017-04-07T12:45:16.123Z
Let problem B be like Max {0,1}-linear programming, but setting all x_i to 0 is a valid solution with 0 quaility. A polynomial-time approximation of problem B could always return those 0-quality solutions, but its performance ratio wouldn't be exponentially bounded with the size of the problem, as required by Exp-APX. Actually, its performance ratio would be infinite: Quality_of_optimal_solution / Quality_of_returned_solution = infinite. It would be different if all instances admitted a 1-quality solution though.
EXPTIME-complete
CC BY-SA 3.0
2017-04-07T13:18:27.663Z
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
CC BY-SA 3.0
2017-04-07T19:48:00.667Z
I've just checked a few other definitions and you're right. Since objective values are positive integers, they cannot be 0, so my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". Under that new definition, problem A could be NPO-complete. So I think you've solved my question, thanks Markus! :-) Write it as the answer if you wish.
EXPTIME-complete
CC BY-SA 3.0
2017-04-07T22:04:25.550Z
By the way, why do NPO-complete problems turn into Exp-APX-complete problems just by adding a 1-valued dummy solution? I understand why these new problems would be in Exp-APX, as a polynomial-time objective function cannot return a value higher than 2^q(n) for some polynomial q, and the ratio between 2^q(n) and 1 is exponential. However, why would it necessarily be Exp-APX-hard? How is this hardness "inherited" from its former NPO-hardness?
EXPTIME-complete
<complexity-classes><approximation-algorithms><approximation-hardness><approximation>
Looking for approximation class between NPO and Exp-APX
EXPTIME-complete
# Looking for approximation class between NPO and Exp-APX

(Asked by: username_0 on 2017-04-06)

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?

**Tags:** complexity-classes, approximation-algorithms, approximation-hardness, approximation

> **Comments:**
> **username_1**: 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  
> **username_0**: RQ1: So the version of TSP which is Exp-APX-complete requires all pairs to be connected and edge costs be at least 1, this is what I supposed, thank you. RQ2: Is it in APX even if graphs are general (i.e. no metric or geometric constraint)?  
> **username_1**: 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".  
> **username_1**: 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).  
> **username_0**: About RQ1: You are right, the connectiviy of all pairs is a sufficient but not necessary condition. We need graphs where we can find at least one Hamiltonian cycle in polynomial time (otherwise no polynomial-time approximation could always find some solution). This happens indeed if all pairs of nodes are connected, but it is not necessary.  
> **username_0**: About RQ2: Thanks for the info. So in order to prove the Exp-APX-hardness of my problem A, now I know I cannot e.g. AP-reduce Max TSP into A. It's a pity, as reductions where both problems are max or both problems are min are typically more intuitive, but I don't know any Exp-APX-complete maximization problem.  
> **username_2**: 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.  
> **username_0**: Let problem B be like Max {0,1}-linear programming, but setting all x_i to 0 is a valid solution with 0 quaility. A polynomial-time approximation of problem B could always return those 0-quality solutions, but its performance ratio wouldn't be exponentially bounded with the size of the problem, as required by Exp-APX. Actually, its performance ratio would be infinite: Quality_of_optimal_solution / Quality_of_returned_solution = infinite. It would be different if all instances admitted a 1-quality solution though.  
> **username_2**: 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.  
> **username_0**: I've just checked a few other definitions and you're right. Since objective values are positive integers, they cannot be 0, so my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". Under that new definition, problem A could be NPO-complete. So I think you've solved my question, thanks Markus! :-) Write it as the answer if you wish.  
> **username_0**: By the way, why do NPO-complete problems turn into Exp-APX-complete problems just by adding a 1-valued dummy solution? I understand why these new problems would be in Exp-APX, as a polynomial-time objective function cannot return a value higher than 2^q(n) for some polynomial q, and the ratio between 2^q(n) and 1 is exponential. However, why would it necessarily be Exp-APX-hard? How is this hardness "inherited" from its former NPO-hardness?  

---

## 1 answers

### Answer by username_0 on 2017-04-25. Score: 1 | Accepted answer

As pointed out by username_2 in the comments section, objective values must be positive integers, so they cannot be 0. Hence my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". In fact, under that new definition, problem A turns out to be NPO-complete.


---

