Optimization and Tropical Geometry

This is a BMS Advanced Course which is part of the Thematic Einstein Semester Network Games, Tropical Geometry and Quantum Communication. The course takes place on Mondays, 10-12, in MA 041 at TU Berlin.

Teaching assistant: Robert Löwe

Contents

  1. Shortest Paths and the Hungarian Method [15 April]; notes and exercises/problems
  2. Tropical Hypersurfaces [29 April]; notes and exercises/problems
  3. Tropical Linear Programming, MEAN-PAYOFF and Semi-Algebraic Sets [06 May]; notes and exercises/problems
  4. Product-Mix Auctions [13 May]; notes, ipynb for polymake 3.4 and exercises/problems
  5. Multicriteria Optimization and Alexander Duality of Monomial Ideals [20 May]; notes and exercises/problems
  6. Divisors on Curves, Riemann-Roch and Chip Firing Games [27 May]; notes and exercises/problems

This course will be followed by an international conference (hosted at ZIB in June) and subsequent project work. For each lecture I will provide a set of problems that the participants are expected to work on, on their own. The final jour fixe before the projects start (on Wednesday, 29 May, 10:15 in MA 315 at TU) provides an excellent opportunity for exchange on those problems and to ask questions.

Participants of the TES are expected to work on projects to be presented at the final workshop on 1 July (hosted at ZIB).

The Kickoff Meeting took place on 09 April, 18:00 at Mathematische Fachbibliothek, TU Berlin.

References

Akian, Marianne, Stéphane Gaubert, and Alexander Guterman. 2012. “Tropical Polyhedra Are Equivalent to Mean Payoff Games.” Internat. J. Algebra Comput. 22 (1): 1250001, 43.

Alessandrini, Daniele. 2013. “Logarithmic Limit Sets of Real Semi-Algebraic Sets.” Adv. Geom. 13 (1): 155–90. doi:10.1515/advgeom-2012-0020.

Allamigeon, Xavier, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. 2014. “Combinatorial Simplex Algorithms Can Solve Mean Payoff Games.” SIAM J. Opt. 24 (4): 2096–2117. doi:10.1137/140953800.

———. 2015. “Tropicalizing the Simplex Algorithm.” SIAM J. Discrete Math. 29 (2): 751–95. doi:10.1137/130936464.

———. 2018. “Log-Barrier Interior Point Methods Are Not Strongly Polynomial.” SIAM J. Appl. Algebra Geom. 2 (1): 140–78. doi:10.1137/17M1142132.

Allamigeon, Xavier, Stéphane Gaubert, and Ricardo D. Katz. 2011. “The Number of Extreme Points of Tropical Polyhedra.” J. Combin. Theory Ser. A 118 (1): 162–89. doi:10.1016/j.jcta.2010.04.003.

Allamigeon, Xavier, Stéphane Gaubert, and Mateusz Skomra. 2018. “Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms.” J. Symbolic Comput. 85: 25–54. doi:10.1016/j.jsc.2017.07.002.

Baker, Matthew, and Serguei Norine. 2007. “Riemann-Roch and Abel-Jacobi Theory on a Finite Graph.” Adv. Math. 215 (2): 766–88.

Baldwin, Elizabeth, and Paul Klemperer. 2015. “Understanding Preferences: ‘Demand Types’, and the Existence of Equilibrium with Indivisibilities.” http://www.nuff.ox.ac.uk/users/klemperer/demandtypes.pdf.

Balletti, Gabriele, Marta Panizzut, and Bernd Sturmfels. 2018. “K3 Polytopes and Their Quartic Surfaces.” https://arxiv.org/abs/1806.02236.

Bourbaki, Nicolas. 2002. Lie Groups and Lie Algebras. Chapters 4–6. Elements of Mathematics (Berlin). Springer-Verlag, Berlin. doi:10.1007/978-3-540-89394-3.

Butkovič, Peter. 2010. Max-Linear Systems: Theory and Algorithms. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London. doi:10.1007/978-1-84996-299-5.

Danilov, Vladimir, Gleb Koshevoy, and Kazuo Murota. 2001. “Discrete Convexity and Equilibria in Economies with Indivisible Goods and Money.” Math. Social Sci. 41 (3): 251–73. doi:10.1016/S0165-4896(00)00071-8.

Dächert, Kerstin, Kathrin Klamroth, Renaud Lacour, and Daniel Vanderpooten. 2017. “Efficient Computation of the Search Region in Multi-Objective Optimization.” European J. Oper. Res. 260 (3): 841–55. doi:10.1016/j.ejor.2016.05.029.

De Loera, Jesús A., Jörg Rambau, and Francisco Santos. 2010. Triangulations. Vol. 25. Algorithms and Computation in Mathematics. Berlin: Springer-Verlag.

Decker, Wolfram, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann. 2019. “Singular 4-1-2 — A Computer Algebra System for Polynomial Computations.” http://www.singular.uni-kl.de.

Di Rocco, Sandra, David Eklund, and Madeleine Weinstein. 2019. “The Bottleneck Degree of Algebraic Varieties.” https://arxiv.org/abs/1904.04502.

Dörfler, Daniel, and Andreas Löhne. 2018. “Geometric Duality and Parametric Duality for Multiple Objective Linear Programs Are Equivalent.” J. Nonlinear Convex Anal. 19 (7): 1181–8.

Ehrenfeucht, Andrzej, and Jan Mycielski. 1979. “Positional Strategies for Mean Payoff Games.” Internat. J. Game Theory 8 (2): 109–13. doi:10.1007/BF01768705.

Einsiedler, Manfred, Mikhail Kapranov, and Douglas Lind. 2006. “Non-Archimedean Amoebas and Tropical Varieties.” J. Reine Angew. Math. 601: 139–57.

Filip, Simion. 2019. “Tropical Dynamics of Area-Preserving Maps.” https://arxiv.org/abs/1903.00794.

Gallo, Giorgio, Michael D. Grigoriadis, and Robert E. Tarjan. 1989. “A Fast Parametric Maximum Flow Algorithm and Applications.” SIAM J. Comput. 18 (1): 30–55. doi:10.1137/0218003.

Gathmann, Andreas, and Michael Kerber. 2008. “A Riemann-Roch Theorem in Tropical Geometry.” Math. Z. 259 (1): 217–30.

Gawrilow, Ewgenij, and Michael Joswig. 2000. “Polymake: A Framework for Analyzing Convex Polytopes.” In Polytopes—Combinatorics and Computation (Oberwolfach, 1997), 29:43–73. DMV Sem. Basel: Birkhäuser.

Grayson, Daniel R., and Michael E. Stillman. n.d. “Macaulay2, a Software System for Research in Algebraic Geometry.” http://www.math.uiuc.edu/Macaulay2/.

Haase, Christian, Gregg Musiker, and Josephine Yu. 2012. “Linear Systems on Tropical Curves.” Math. Z. 270 (3-4): 1111–40. doi:10.1007/s00209-011-0844-4.

Haase, Christian, Andreas Paffenholz, Lindsay C. Piechnik, and Francisco Santos. to appear. “Existence of Unimodular Triangulations — Positive Results.” Mem. AMS. https://arxiv.org/abs/1405.1687.

Hamel, Andreas H., and Andreas Löhne. 2018. “A Set Optimization Approach to Zero-Sum Matrix Games with Multi-Dimensional Payoffs.” Math. Methods Oper. Res. 88 (3): 369–97. doi:10.1007/s00186-018-0639-z.

Hampe, Simon, and Michael Joswig. 2017. “Tropical Computations in Polymake.” In Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory, edited by Gebhard Böckle, Wolfram Decker, and Gunter Malle, 361–85. Springer, Cham.

Hoşten, Serkan, and Walter D. Morris Jr. 1999. “The Order Dimension of the Complete Graph.” Discrete Math. 201 (1-3): 133–39. doi:10.1016/S0012-365X(98)00315-X.

Jell, Philipp, Claus Scheiderer, and Josephine Yu. 2018. “Real Tropicalization and Analytification of Semialgebraic Sets.” https://arxiv.org/abs/1810.05132.

Joswig, Michael. 2019. Essentials of Tropical Combinatorics. Springer, to appear. http://www.math.tu-berlin.de/~joswig/etc.

Joswig, Michael, and Georg Loho. 2017. “Monomial Tropical Cones for Multicriteria Optimization.” https://arxiv.org/abs/1707.09305.

Joswig, Michael, and Benjamin Schröter. 2019. “The Tropical Geometry of Shortest Paths.” https://arxiv.org/abs/1904.01082.

Joswig, Michael, Marta Panizzut, and Bernd Sturmfels. 2019. “The Schläfli Fan.” https://arxiv.org/abs/1905.11951.

Klamroth, Kathrin, Renaud Lacour, and Daniel Vanderpooten. 2015. “On the Representation of the Search Region in Multi-Objective Optimization.” European J. Oper. Res. 245 (3): 767–78. doi:10.1016/j.ejor.2015.03.031.

Maclagan, Diane, and Bernd Sturmfels. 2015. Introduction to Tropical Geometry. Vol. 161. Graduate Studies in Mathematics. American Mathematical Society, Providence, RI.

Miller, Ezra, and Bernd Sturmfels. 2005. Combinatorial Commutative Algebra. Vol. 227. Graduate Texts in Mathematics. Springer-Verlag, New York.

Möhring, Rolf H., Martin Skutella, and Frederik Stork. 2004. “Scheduling with AND/OR Precedence Constraints.” SIAM J. Comput. 33 (2): 393–415. doi:10.1137/S009753970037727X.

Paffenholz, Andreas. 2017. “PolyDB: A Database for Polytopes and Related Objects.” In Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory, 533–47. Springer, Cham.

Schrijver, Alexander. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Vol. A. Vol. 24. Algorithms and Combinatorics. Berlin: Springer-Verlag.

Tran, Ngoc Mai, and Josephine Yu. 2015. “Product-Mix Auctions and Tropical Geometry.” https://arxiv.org/abs/1505.05737.

Zwick, Uri, and Mike Paterson. 1996. “The Complexity of Mean Payoff Games on Graphs.” Theoret. Comput. Sci. 158 (1-2): 343–59. doi:10.1016/0304-3975(95)00188-3.


Home Teaching Presentations Projects Software

Last modified: Wed May 29 12:37:00 UTC 2019 by joswig