3

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?

Kaveh
  • 21,577
  • 8
  • 82
  • 183
ilyaraz
  • 1,569
  • 18
  • 33
  • 3
    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). – Tsuyoshi Ito May 28 '12 at 18:07
  • fair enough, but what if we allow some (small) additive error? – ilyaraz May 28 '12 at 18:08
  • Then what is the difference between maximizing the number of satisfied triples and minimizing the number of unsatisfied triples? – Tsuyoshi Ito May 28 '12 at 18:09
  • 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. – ilyaraz May 28 '12 at 18:12
  • 2
    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). – Tsuyoshi Ito May 28 '12 at 18:16
  • My bad. But then what if we allow both multiplicative and additive error, or allow an additive error to depend of OPT. – ilyaraz May 28 '12 at 18:18

1 Answers1

2

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.

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106