3
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gamow
    Apr 6, 2017 at 11:47
  • 1
    $\begingroup$ 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". $\endgroup$
    – Gamow
    Apr 6, 2017 at 11:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – Gamow
    Apr 6, 2017 at 12:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Markus Bläser
    Apr 7, 2017 at 8:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Markus Bläser
    Apr 7, 2017 at 13:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.