[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A geometric approach to betweenness

  • Session 4. Chair: Marek Karpinski
  • Conference paper
  • First Online:
Algorithms — ESA '95 (ESA 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 979))

Included in the following conference series:

Abstract

An input to the betweenness problem contains m constraints over n real variables. Each constraint consists of three variables, where one of the variables is specified to lie inside the interval defined by the other two. The order of the other two variables (which one is the largest and which one is the smallest) is not specified. This problem comes up in questions related to physical mapping in computational molecular biology. In 1979, Opatrny has shown that the problem of deciding whether the n variables can be totally ordered while satisfying the m betweenness constraints is NP-complete. Furthermore, the problem is MAX SNP complete. Therefore, there is some ε>0 such that finding a total order which satisfies at least m(1−ε) of the constraints (even if they are all satisfiable) is NP-hard. It is easy to find an ordering of the variables which satisfies 1/3 of the m constraints (e.g. by choosing the ordering at random).

In this work we present a polynomial time algorithm which either determines that there is no feasible solution, or finds a total order which satisfies at least 1/2 of the m constraints. Our algorithm translates the problem into a set of quadratic inequalities, and solves a semidefinite relaxation of them in \(\mathcal{R}^n\). The n solution points are then projected on a random line through the origin. Using simple geometric properties of the SDP solution, we prove the claimed performance guarantee.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. N. Alon and N. Kahale. “Approximating the independence number via the θ-function”, Manuscript, August 1994.

    Google Scholar 

  2. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. “Proof Verification and Hardness of Approximation Problems”, Proceedings 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 14–23, 1992.

    Google Scholar 

  3. D. Cox, M. Burmeister, E. Price, S. Kim, R. Myers, “Radiation Hybrid Mapping: A Somatic Cell Genetic Method for Constructing High Resolution Maps of Mammalian Chromosomes”, Science, Vol. 250, 1990, pp. 245–250.

    PubMed  Google Scholar 

  4. U. Feige and M. Goemans. “Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT”, Proceedings of the Third Israel Symposium on Theory and Computing Systems, 1995.

    Google Scholar 

  5. M. Goemans and D. Williamson. “.878-Approximation Algorithms for MAX CUT and MAX 2SAT”, Proceedings of the Twenty-Sixth ACM Symposium on Theory of Computing, pp. 422–431, 1994.

    Google Scholar 

  6. S. Goss and H. Harris, “New Methods for Mapping Genes in Human Chromosomes”, Nature, Vol. 255, 1975, pp. 680–684.

    PubMed  Google Scholar 

  7. M. Grötschel, L. Lovász and A. Schrijver. “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1:169–197, 1981.

    Google Scholar 

  8. M. Grötschel, L. Lovász and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, 1987.

    Google Scholar 

  9. R. Hariharan and S. Mahajan. Derandomization of Semidefinite Programming based algorithms. Manuscript, 1995.

    Google Scholar 

  10. D. Karger, R. Motwani and M. Sudan. “Approximate graph coloring via semidefinite programming”, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994.

    Google Scholar 

  11. L. Khaciyan. “A polynomial algorithm in linear programming”, (English translation appears in) Soviet Mathematics Doklady, vol. 20, pp. 191–194, 1979.

    Google Scholar 

  12. L. Lovász. “On the Shannon capacity of a graph”, IEEE Transactions on Information Theory, IT-25:1–7, 1979.

    Article  Google Scholar 

  13. J. Opatrny, “Total Ordering Problem”, SIAM J. Comput., vol. 8 No. 1, February 1979, pp. 111–114.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Technion, 32000, Haifa, Israel

    Benny Chor

  2. IBM Thomas J. watson Research Center, P.O.Box 218, 10598, Yorktown Heights, NY

    Madhu Sudan

Authors
  1. Benny Chor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Madhu Sudan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Paul Spirakis

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chor, B., Sudan, M. (1995). A geometric approach to betweenness. In: Spirakis, P. (eds) Algorithms — ESA '95. ESA 1995. Lecture Notes in Computer Science, vol 979. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60313-1_146

Download citation

  • DOI: https://doi.org/10.1007/3-540-60313-1_146

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60313-9

  • Online ISBN: 978-3-540-44913-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation