Skip to main content
SpringerLink
Log in
Book cover

International Conference on Integer Programming and Combinatorial Optimization

IPCO 2016: Integer Programming and Combinatorial Optimization pp 14–25Cite as

Centerpoints: A Link Between Optimization and Convex Geometry

  • Conference paper
  • First Online:

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9682))

Abstract

We introduce a concept that generalizes several different notions of a “centerpoint” in the literature. We develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are “best possible” in a certain sense. Motivated by this, we establish several structural results about this concept and provide efficient algorithms for computing these points.

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

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

Notes

  1. 1.

    The reader who is unfamiliar with measure theory, may simply consider \(\mu \) to be the volume measure or the mixed-integer measure on the mixed-integer lattice, i.e., \(\mu (S)\) returns the volume of S or the “mixed-integer volume” of the mixed-integer lattice points inside S, where S will usually be a convex body. The “mixed-integer volume” reduces to the number of integer points when the lattice is the set of integer points. See (3) for a precise definition which generalizes both the standard volume and the “counting measure” for the integer lattice.

References

  1. Averkov, G.: On maximal S-free sets and the helly number for the family of s-convex sets. SIAM J. Discrete Math. 27(3), 1610–1624 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Averkov, G., Weismantel, R.: Transversal numbers over subsets of linear spaces. Adv. Geom. 12(1), 19–28 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. Baldoni, V., Berline, N., Koeppe, M., Vergne, M.: Intermediate sums on polyhedra: computation and real Ehrhart theory. Mathematika 59(01), 1–22 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bertsimas, D., Vempala, S.: Solving convex programs by random walks. J. ACM 51(4), 540–556 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  5. Braß, P., Heinrich-Litan, L., Morin, P.: Computing the center of area of a convex polygon. Int. J. Comput. Geom. Appl. 13(05), 439–445 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  6. De Loera, J.A., La Haye, R.N., Oliveros, D., Roldán-Pensado, E.: Helly numbers of algebraic subsets of \(\mathbb{R}^d\). arXiv preprint arXiv:1508.02380 (2015)

  7. Dyckerhoff, R., Mozharovskyi, P.: Exact computation of halfspace depth. arXiv preprint arXiv:1411.6927v2 (2015)

  8. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics: Study and Research Texts, vol. 2. Springer, Berlin (1988)

    MATH  Google Scholar 

  9. Grünbaum, B.: Partitions of mass-distributions and of convex bodies by hyperplanes. Pac. J. Math. 10, 1257–1261 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  10. Grünbaum, B.: Measures of symmetry for convex sets. In: Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, vol. 7, p. 233. American Mathematical Society (1963)

    Google Scholar 

  11. Hoffman, A.J.: Binding constraints and helly numbers. Ann. N. Y. Acad. Sci. 319, 284–288 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  12. Korkine, A.N., Zolotareff, Y.I.: Sur les formes quadratiques. Math. Ann. 6(3), 366–389 (1873)

    Article  MathSciNet  Google Scholar 

  13. Lenstra Jr., H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538–548 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  14. Liu, R.Y., Serfling, R.J., Souvaine, D.L.: Data Depth: Robust Multivariate Analysis, Computational Geometry, and Applications, vol. 72. American Mathematical Society, Providence (2006)

    MATH  Google Scholar 

  15. Mosler, K.: Depth statistics. In: Becker, C., Fried, R., Kuhnt, S. (eds.) Robustness and Complex Data Structures, pp. 17–34. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  16. Nesterov, Y.: Introductory Lectures on Convex Optimization. Applied Optimization, vol. 87. Kluwer Academic Publishers, Boston (2004)

    MATH  Google Scholar 

  17. Pak, I.: On sampling integer points in polyhedra. In: Foundations of computational mathematics (Hong Kong, 2000), pp. 319–324. World Sci. Publ., River Edge (2002)

    Google Scholar 

  18. Rousseeuw, P.J., Ruts, I.: The depth function of a population distribution. Metrika 49(3), 213–244 (1999)

    MathSciNet  MATH  Google Scholar 

  19. Talagrand, M.: Sharper bounds for gaussian and empirical processes. Ann. Probab. 22, 28–76 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  20. Tukey, J.W.: Mathematics and the picturing of data. In: Proceedings of the International Congress of Mathematicians, vol. 2, pp. 523–531 (1975)

    Google Scholar 

  21. Vapnik, V.N., Chervonenkis, A.Ya.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264–280 (1971)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Johns Hopkins University, Baltimore, USA

    Amitabh Basu

  2. Cardiff University, Cardiff, UK

    Timm Oertel

Authors
  1. Amitabh Basu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Timm Oertel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Timm Oertel .

Editor information

Editors and Affiliations

  1. Université de Liège, Liège, Belgium

    Quentin Louveaux

  2. Technische Universität Berlin, Berlin, Germany

    Martin Skutella

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Basu, A., Oertel, T. (2016). Centerpoints: A Link Between Optimization and Convex Geometry. In: Louveaux, Q., Skutella, M. (eds) Integer Programming and Combinatorial Optimization. IPCO 2016. Lecture Notes in Computer Science(), vol 9682. Springer, Cham. https://doi.org/10.1007/978-3-319-33461-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-33461-5_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-33460-8

  • Online ISBN: 978-3-319-33461-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation