3
$\begingroup$

Is there any non-trivial approximation algorithm for a variant of betweenness problem: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?

$\endgroup$
6
  • 3
    $\begingroup$ You cannot hope for any multiplicative approximation because it is NP-complete to decide whether all triples can be simultaneously satisfied or not (the original, decision version of betweenness). $\endgroup$ Commented May 28, 2012 at 18:07
  • $\begingroup$ fair enough, but what if we allow some (small) additive error? $\endgroup$
    – ilyaraz
    Commented May 28, 2012 at 18:08
  • $\begingroup$ Then what is the difference between maximizing the number of satisfied triples and minimizing the number of unsatisfied triples? $\endgroup$ Commented May 28, 2012 at 18:09
  • $\begingroup$ I don't see how an algorithm with an additive error 1 for the minimization problem is implied by any known algorithm for the maximization version. $\endgroup$
    – ilyaraz
    Commented May 28, 2012 at 18:12
  • 2
    $\begingroup$ Well, that is because an algorithm with an additive error 1 in the minimization version is equivalent to an algorithm with an additive error 1 in the maximization version (which does not exist unless P=NP). $\endgroup$ Commented May 28, 2012 at 18:16

1 Answer 1

2
$\begingroup$

The particular minimization version which you mentioned does not make much sense, because even deciding whether all triples can be satisfied simutaneously or not is NP-comlpete. Also, it is easy to see that unless P=NP, for every choice of constants k1 and k2, there is no polynomial-time approximation algorithm for the minimization version of the betweenness problem in the sense that it produces an assignment which violates at most (k1⋅OPT + k2) triples, where OPT is the minimum number of violated triples. (Just consider the case where OPT=0.) [Edit: In an earlier revision, I stated that this follows from [CS98], but [CS98] was overkill for it.]

On a tangentially related topic, if you consider the additive approximation of the ratio of (un)satisfied triples, the problem becomes much more interesting. Chor and Sudan [CS98] showed that for every s∈(47/48,1), it is NP-complete to decide whether a given instance of the betweenness problem is satisfiable or no assignment satisfies more than s fraction of constraints. In particular, the ratio version is NP-hard to approximate within any constant additive error less than 1/48, and this clearly applies equally to both the maximization version and the minimization version.

For more on approximation of a satisfaction ratio within an additive error, see my answer to the question “Hardness of approximation - additive error” by Raphael Clifford.

[CS98] Benny Chor and Madhu Sudan. A geometric approach to betweenness. SIAM Journal on Discrete Mathematics, 11(4):511–523, Nov. 1998. DOI: 10.1137/S0895480195296221.

$\endgroup$

Your Answer

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

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