159:. It remains hard to solve or approximate even for dense instances that include an ordered triple for each possible unordered triple of items. The minimum version of the problem restricted to the tournaments was proven to have polynomial time approximation schemes (PTAS). One can achieve an approximation ratio of 1/3 (in expectation) by ordering the items randomly, and this simple strategy gives the best possible polynomial-time approximation if the
221:. Certain types of genetic experiments can be used to determine the ordering of triples of genetic markers, but do not distinguish a genetic sequence from its reversal, so the information yielded from such an experiment determines only which one out of three markers is the middle one. The betweenness problem is an abstraction of the problem of assembling a collection of markers into a single sequence given experimental data of this type.
140:. However, it can easily be solved when all unordered triples of items are represented by an ordered triple of the input, by choosing one of the two items that are not between any others to be the start of the ordering and then using the triples involving this item to compare the relative positions of each pair of remaining items.
105:
If an input contains two triples like (1,2,3) and (2,3,1) with the same three items but a different choice of the middle item, then there is no valid solution. However, there are more complicated ways of forming a set of triples with no valid solution, that do not contain such a pair of contradictory
101:
In the first of these output orderings, for all five of the input triples, the middle item of the triple appears between the other two items
However, for the second output ordering, item 4 is not between items 1 and 2, contradicting the requirement given by the triple (2,4,1).
69:, with the property that for each of the given triples, the middle item in the triple appears in the output somewhere between the other two items. The items of each triple are not required to be consecutive in the output.
437:
Karpinski, Marek; Schudy, Warren (2011), "Approximation schemes for the betweenness problem in tournaments and related ranking problems", in L.A. Goldberg and K. Jansen and R.Ravi and J.D.P. Rolim (ed.),
592:
587:
516:
469:
271:
167:
or combinatorial methods to find an ordering that satisfies at least half of the triples of any satisfiable instance, in polynomial time.
443:
41:
about ordering a collection of items subject to constraints that some items must be placed between others. It has applications in
317:
699:
400:
359:
179:
171:
164:
121:
of the betweenness problem (in which an algorithm must decide whether or not there exists a valid solution) is
160:
126:
20:
704:
645:
496:
148:
34:
675:
657:
627:
601:
530:
475:
447:
512:
465:
334:
19:
This article is about ordering items with constraints. For centrality in social networks, see
499:; Manokaran, Rajsekar (2009), "Every permutation CSP of arity 3 is approximation resistant",
143:
The related problem of finding an ordering that maximizes the number of satisfied triples is
667:
611:
590:; Mnich, Matthias; Yeo, Anders (2010), "Betweenness parameterized above tight lower bound",
557:
504:
457:
409:
368:
326:
280:
202:
144:
130:
118:
24:
623:
569:
526:
423:
380:
292:
619:
565:
522:
419:
376:
288:
152:
548:
Makarychev, Yury (2012), "Simple linear time approximation algorithm for betweenness",
492:
214:
137:
62:
42:
693:
583:
205:
can find solutions to many instances of the betweenness problem arising in practice.
679:
631:
479:
218:
38:
534:
461:
312:
266:
225:
122:
66:
46:
615:
671:
561:
284:
262:
134:
414:
395:
229:
330:
338:
508:
174:, the problem of satisfying as many constraints as possible from a set
156:
372:
65:
of items. The items listed in these triples should be placed into a
662:
648:; Wu, Baoyindureng (2011), "On Reichenbach's causal betweenness",
606:
452:
233:
224:
The betweenness problem has also been used to model theories of
315:(1997), "Building human genome maps with radiation hybrids",
198:|/3 quality guaranteed in expectation by a random ordering.
501:
61:
The input to a betweenness problem is a collection of
311:Slonim, Donna; Kruglyak, Leonid; Stein, Lincoln;
23:. For the betweenness relation in geometry, see
269:(1998), "A geometric approach to betweenness",
147:, implying that it is impossible to achieve an
77:As an example, the collection of input triples
357:OpatrnĂ˝, J. (1979), "Total ordering problem",
194:found by the parameterized algorithm and the |
8:
398:(2007), "Hardness of fully dense problems",
81:(2,1,3), (3,4,5), (1,4,5), (2,4,1), (5,2,3)
661:
605:
451:
413:
213:One application of betweenness arises in
306:
304:
302:
593:Journal of Computer and System Sciences
245:
133:and also by a different reduction from
114:
50:
257:
255:
253:
251:
249:
201:Although not guaranteed to succeed, a
352:
350:
348:
182:when parameterized by the difference
7:
446:, vol. 6845, pp. 277–288,
272:SIAM Journal on Discrete Mathematics
163:is true. It is also possible to use
85:is satisfied by the output ordering
14:
444:Lecture Notes in Computer Science
190:|/3 between the solution quality
318:Journal of Computational Biology
151:arbitrarily close to 1 in
440:Proc. APPROX 2011, RANDOM 2011
1:
462:10.1007/978-3-642-22935-0_24
217:, as part of the process of
550:Operations Research Letters
401:Information and Computation
279:(4): 511–523 (electronic),
721:
616:10.1016/j.jcss.2010.05.001
18:
672:10.1007/s10670-011-9321-z
562:10.1016/j.orl.2012.08.008
360:SIAM Journal on Computing
285:10.1137/S0895480195296221
180:fixed-parameter tractable
16:Algorithm in order theory
415:10.1016/j.ic.2007.02.006
172:parameterized complexity
165:semidefinite programming
161:unique games conjecture
331:10.1089/cmb.1997.4.487
21:betweenness centrality
497:Guruswami, Venkatesan
700:NP-complete problems
186: − |
45:and was shown to be
509:10.1109/CCC.2009.29
149:approximation ratio
35:algorithmic problem
503:, pp. 62–73,
178:of constraints is
125:in two ways, by a
518:978-0-7695-3717-7
471:978-3-642-22934-3
57:Problem statement
712:
684:
682:
665:
642:
636:
634:
609:
580:
574:
572:
545:
539:
537:
489:
483:
482:
455:
434:
428:
426:
417:
408:(8): 1117–1129,
391:
385:
383:
354:
343:
341:
308:
297:
295:
259:
203:greedy heuristic
131:3-satisfiability
119:decision version
117:showed that the
25:ordered geometry
720:
719:
715:
714:
713:
711:
710:
709:
690:
689:
688:
687:
644:
643:
639:
582:
581:
577:
547:
546:
542:
519:
493:Charikar, Moses
491:
490:
486:
472:
436:
435:
431:
393:
392:
388:
373:10.1137/0208008
356:
355:
346:
310:
309:
300:
261:
260:
247:
242:
211:
153:polynomial time
112:
75:
63:ordered triples
59:
28:
17:
12:
11:
5:
718:
716:
708:
707:
702:
692:
691:
686:
685:
646:Chvátal, Vašek
637:
600:(8): 872–878,
584:Gutin, Gregory
575:
556:(6): 450–452,
540:
517:
484:
470:
429:
386:
367:(1): 111–114,
344:
325:(4): 487–504,
298:
244:
243:
241:
238:
215:bioinformatics
210:
207:
115:OpatrnĂ˝ (1979)
111:
108:
99:
98:
97:3, 1, 2, 4, 5.
91:
90:
83:
82:
74:
71:
58:
55:
51:OpatrnĂ˝ (1979)
43:bioinformatics
15:
13:
10:
9:
6:
4:
3:
2:
717:
706:
703:
701:
698:
697:
695:
681:
677:
673:
669:
664:
659:
655:
651:
647:
641:
638:
633:
629:
625:
621:
617:
613:
608:
603:
599:
595:
594:
589:
588:Kim, Eun Jung
585:
579:
576:
571:
567:
563:
559:
555:
551:
544:
541:
536:
532:
528:
524:
520:
514:
510:
506:
502:
498:
494:
488:
485:
481:
477:
473:
467:
463:
459:
454:
449:
445:
441:
433:
430:
425:
421:
416:
411:
407:
403:
402:
397:
390:
387:
382:
378:
374:
370:
366:
362:
361:
353:
351:
349:
345:
340:
336:
332:
328:
324:
320:
319:
314:
307:
305:
303:
299:
294:
290:
286:
282:
278:
274:
273:
268:
264:
258:
256:
254:
252:
250:
246:
239:
237:
235:
231:
227:
222:
220:
216:
208:
206:
204:
199:
197:
193:
189:
185:
181:
177:
173:
168:
166:
162:
158:
154:
150:
146:
141:
139:
136:
132:
128:
124:
120:
116:
109:
107:
103:
96:
95:
94:
89:3, 1, 4, 2, 5
88:
87:
86:
80:
79:
78:
72:
70:
68:
64:
56:
54:
52:
48:
44:
40:
36:
32:
26:
22:
705:Order theory
656:(1): 41–48,
653:
649:
640:
597:
591:
578:
553:
549:
543:
500:
487:
439:
432:
405:
399:
394:Ailon, Nir;
389:
364:
358:
322:
316:
313:Lander, Eric
276:
270:
267:Sudan, Madhu
223:
219:gene mapping
212:
209:Applications
200:
195:
191:
187:
183:
175:
169:
142:
113:
104:
100:
92:
84:
76:
60:
39:order theory
30:
29:
263:Chor, Benny
226:probability
145:MAXSNP-hard
123:NP-complete
93:but not by
67:total order
47:NP-complete
31:Betweenness
694:Categories
650:Erkenntnis
396:Alon, Noga
240:References
138:2-coloring
135:hypergraph
110:Complexity
663:0902.1763
607:0907.5427
453:0911.2214
230:causality
127:reduction
106:triples.
680:14123568
73:Examples
632:3408698
624:2722353
570:2998680
527:2932455
480:7180847
424:2340896
381:0522973
339:9385541
293:1640920
155:unless
678:
630:
622:
568:
535:257225
533:
525:
515:
478:
468:
422:
379:
337:
291:
232:, and
157:P = NP
33:is an
676:S2CID
658:arXiv
628:S2CID
602:arXiv
531:S2CID
476:S2CID
448:arXiv
129:from
513:ISBN
466:ISBN
335:PMID
234:time
668:doi
612:doi
558:doi
505:doi
458:doi
410:doi
406:205
369:doi
327:doi
281:doi
170:In
49:by
37:in
696::
674:,
666:,
654:76
652:,
626:,
620:MR
618:,
610:,
598:76
596:,
586:;
566:MR
564:,
554:40
552:,
529:,
523:MR
521:,
511:,
495:;
474:,
464:,
456:,
442:,
420:MR
418:,
404:,
377:MR
375:,
363:,
347:^
333:,
321:,
301:^
289:MR
287:,
277:11
275:,
265:;
248:^
236:.
228:,
53:.
683:.
670::
660::
635:.
614::
604::
573:.
560::
538:.
507::
460::
450::
427:.
412::
384:.
371::
365:8
342:.
329::
323:4
296:.
283::
196:C
192:q
188:C
184:q
176:C
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.