<p>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 <i>k</i><sub>1</sub> and <i>k</i><sub>2</sub>, 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 (<i>k</i><sub>1</sub>⋅OPT + <i>k</i><sub>2</sub>) triples, where OPT is the minimum number of violated triples.  (Just consider the case where OPT=0.)  <em>[Edit: In an earlier revision, I stated that this follows from [CS98], but [CS98] was overkill for it.]</em></p>

<p>On a tangentially related topic, if you consider the <em>additive</em> approximation of the <em>ratio</em> of (un)satisfied triples, the problem becomes much more interesting.  Chor and Sudan [CS98] showed that for every <i>s</i>∈(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 <i>s</i> 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.</p>

<p>For more on approximation of a satisfaction ratio within an additive error, see my answer to the question “<a href="https://cstheory.stackexchange.com/questions/2421/hardness-of-approximation-additive-error">Hardness of approximation - additive error</a>” by Raphael Clifford.</p>

<p>[CS98] Benny Chor and Madhu Sudan.  A geometric approach to betweenness.  <em>SIAM Journal on Discrete Mathematics</em>, 11(4):511–523, Nov. 1998.  DOI: <a href="http://dx.doi.org/10.1137/S0895480195296221" rel="nofollow noreferrer">10.1137/S0895480195296221</a>.</p>

CC BY-SA 3.0
2012-05-28T18:46:01.817Z
2012-05-28T19:57:36.640Z
2017-04-13T12:32:28.117Z
Tsuyoshi Ito
<p>Is there any non-trivial approximation algorithm for a variant of <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node255.html" rel="nofollow">betweenness problem</a>: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?</p>

CC BY-SA 3.0
2012-05-28T18:07:22.490Z
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
CC BY-SA 3.0
2012-05-28T18:08:42.377Z
fair enough, but what if we allow some (small) additive error?
ilyaraz
CC BY-SA 3.0
2012-05-28T18:09:50.630Z
Then what is the difference between maximizing the number of satisfied triples and minimizing the number of unsatisfied triples?
Tsuyoshi Ito
CC BY-SA 3.0
2012-05-28T18:12:18.973Z
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
CC BY-SA 3.0
2012-05-28T18:16:01.167Z
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
CC BY-SA 3.0
2012-05-28T18:18:36.173Z
My bad. But then what if we allow both multiplicative and additive error, or allow an additive error to depend of OPT.
ilyaraz
<ds.algorithms><approximation-algorithms><csp>
A variant of betweenness problem
ilyaraz
# A variant of betweenness problem

(Asked by: username_0 on 2012-05-28)

Is there any non-trivial approximation algorithm for a variant of [betweenness problem](http://www.nada.kth.se/~viggo/wwwcompendium/node255.html): namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?

**Tags:** ds.algorithms, approximation-algorithms, csp

> **Comments:**
> **username_1**: 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).  
> **username_0**: fair enough, but what if we allow some (small) additive error?  
> **username_1**: Then what is the difference between maximizing the number of satisfied triples and minimizing the number of unsatisfied triples?  
> **username_0**: 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.  
> **username_1**: 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).  
> **username_0**: My bad. But then what if we allow both multiplicative and additive error, or allow an additive error to depend of OPT.  

---

## 1 answers

### Answer by username_1 on 2012-05-28. Score: 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 *k*1 and *k*2, 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 (*k*1⋅OPT + *k*2) 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](https://cstheory.stackexchange.com/questions/2421/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](http://dx.doi.org/10.1137/S0895480195296221).


---

