Document Open Access Logo

Signed Tropical Convexity

Authors Georg Loho, László A. Végh

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.24.pdf
  • Filesize: 0.66 MB
  • 35 pages

Document Identifiers

Author Details

Georg Loho
  • London School of Economics and Political Science, UK
László A. Végh
  • London School of Economics and Political Science, UK

Funding

Supported by the European Research Council (ERC) Starting Grant ScaleOpt, No. 757481.

Acknowledgements

We thank Daniel Dadush for insisting on balanced numbers and for inspiring discussions on the tropical Fourier-Motzkin elimination. We thank Xavier Allamigeon as well as Stéphane Gaubert for communicating their related work. We are grateful to Matthias Schymura for helping to get an intuition for the unintuitive line segments. Furthermore, we thank Mateusz Skomra and an anonymous referee for pointing out the NP-completeness stated in Theorem 4.21.

Cite AsGet BibTex

Georg Loho and László A. Végh. Signed Tropical Convexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 24:1-24:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.24

Abstract

We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas' lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
Keywords
  • tropical convexity
  • signed tropical numbers
  • Farkas' lemma

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Akian, G. Cohen, S. Gaubert, R. Nikoukhah, and J. P. Quadrat. Linear systems in (max, +) algebra. In 29th IEEE Conference on Decision and Control, pages 151-156 vol.1, December 1990. URL: https://doi.org/10.1109/CDC.1990.203566.
  2. Marianne Akian, Xavier Allamigeon, Stéphane Gaubert, and Sergei Sergeev. Tropical optimization with signs, in preparation. Google Scholar
  3. Marianne Akian, Stéphane Gaubert, and Alexander Guterman. Tropical polyhedra are equivalent to mean payoff games. Internat. J. Algebra Comput., 22(1):1250001, 43, 2012. URL: https://doi.org/10.1142/S0218196711006674.
  4. Marianne Akian, Stéphane Gaubert, and Alexander Guterman. Tropical Cramer determinants revisited. In Tropical and idempotent mathematics and applications, volume 616 of Contemp. Math., pages 1-45. Amer. Math. Soc., Providence, RI, 2014. URL: https://doi.org/10.1090/conm/616/12324.
  5. Marianne Akian, Stéphane Gaubert, and Louis Rowen. Linear algebra over systems, in preparation. Google Scholar
  6. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. Tropicalizing the simplex algorithm. SIAM J. Discrete Math., 29(2):751-795, 2015. URL: https://doi.org/10.1137/130936464.
  7. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM J. Appl. Algebra Geom., 2(1):140-178, 2018. Google Scholar
  8. Xavier Allamigeon, Uli Fahrenberg, Stéphane Gaubert, Ricardo D. Katz, and Axel Legay. Tropical Fourier-Motzkin elimination, with an application to real-time verification. International Journal of Algebra and Computation, 24(05):569-607, 2014. URL: https://doi.org/10.1142/S0218196714500258.
  9. Xavier Allamigeon, Stéphane Gaubert, and Ricardo D. Katz. Tropical polar cones, hypergraph transversals, and mean payoff games. Linear Algebra Appl., 435(7):1549-1574, 2011. URL: https://doi.org/10.1016/j.laa.2011.02.004.
  10. Esther M. Arkin and Christos H. Papadimitriou. On negative cycles in mixed graphs. Oper. Res. Lett., 4(3):113-116, 1985. URL: https://doi.org/10.1016/0167-6377(85)90013-6.
  11. Achim Bachem and Walter Kern. Linear programming duality: an introduction to oriented matroids. Berlin: Springer-Verlag, 1992. Google Scholar
  12. Matthew Baker and Nathan Bowler. Matroids over hyperfields, 2016. URL: http://arxiv.org/abs/1601.01204.
  13. Egon Balas. Disjunctive programming. Ann. Discrete Math., 5:3-51, 1979. Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), II. Google Scholar
  14. Walter Briec. Some remarks on an idempotent and non-associative convex structure. J. Convex Anal., 22(1):259-289, 2015. Google Scholar
  15. Walter Briec and Charles Horvath. B-convexity. Optimization, 53(2):103-127, 2004. URL: https://doi.org/10.1080/02331930410001695283.
  16. Peter Butkovič, Hans Schneider, and Sergei Sergeev. Generators, extremals and bases of max cones. Linear Algebra Appl., 421(2-3):394-406, 2007. URL: https://doi.org/10.1016/j.laa.2006.10.004.
  17. Sergei Chubanov. A polynomial projection algorithm for linear feasibility problems. Math. Program., 153(2, Ser. A):687-713, 2015. URL: https://doi.org/10.1007/s10107-014-0823-8.
  18. Guy Cohen, Stéphane Gaubert, Jean-Pierre Quadrat, and Ivan Singer. Max-plus convex sets and functions. In Idempotent mathematics and mathematical physics, volume 377 of Contemp. Math., pages 105-129. Amer. Math. Soc., Providence, RI, 2005. URL: https://doi.org/10.1090/conm/377/06987.
  19. Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming., volume 271. Cham: Springer, 2014. Google Scholar
  20. Mike Develin and Bernd Sturmfels. Tropical convexity. Doc. Math., 9:1-27, 2004. Google Scholar
  21. Mike Develin and Josephine Yu. Tropical polytopes and cellular resolutions. Experiment. Math., 16(3):277-291, 2007. URL: http://projecteuclid.org/euclid.em/1204928529.
  22. Alex Fink and Felipe Rincón. Stiefel tropical linear spaces. J. Combin. Theory Ser. A, 135:291-331, 2015. URL: https://doi.org/10.1016/j.jcta.2015.06.001.
  23. Stéphane Gaubert and Ricardo D. Katz. The tropical analogue of polar cones. Linear Algebra Appl., 431(5-7):608-625, 2009. URL: https://doi.org/10.1016/j.laa.2009.03.012.
  24. Stéphane Gaubert and Ricardo D. Katz. Minimal half-spaces and external representation of tropical polyhedra. J. Algebraic Combin., 33(3):325-348, 2011. URL: https://doi.org/10.1007/s10801-010-0246-4.
  25. Dima Grigoriev and Vladimir V. Podolskii. Tropical effective primary and dual Nullstellensätze. Discrete Comput. Geom., 59(3):507-552, 2018. URL: https://doi.org/10.1007/s00454-018-9966-3.
  26. V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan. Cyclic games and finding minimax mean cycles in digraphs. Zh. Vychisl. Mat. i Mat. Fiz., 28(9):1407-1417, 1439, 1988. Google Scholar
  27. Philipp Jell, Claus Scheiderer, and Josephine Yu. Real tropicalization and analytification of semialgebraic sets, 2018. URL: http://arxiv.org/abs/1810.05132.
  28. Michael Joswig and Georg Loho. Weighted digraphs and tropical cones. Linear Algebra Appl., 501:304-343, 2016. URL: https://doi.org/10.1016/j.laa.2016.02.027.
  29. Victor Klee, Richard Ladner, and Rachel Manber. Signsolvability revisited. Linear Algebra Appl., 59:131-157, 1984. URL: https://doi.org/10.1016/0024-3795(84)90164-2.
  30. Marc Krasner. A class of hyperrings and hyperfields. Internat. J. Math. Math. Sci., 6(2):307-311, 1983. URL: https://doi.org/10.1155/S0161171283000265.
  31. Rolf H. Möhring, Martin Skutella, and Frederik Stork. Scheduling with AND/OR precedence constraints. SIAM J. Comput., 33(2):393-415, 2004. URL: https://doi.org/10.1137/S009753970037727X.
  32. Louis Rowen. Algebras with a negation map, 2016. URL: http://arxiv.org/abs/1602.00353.
  33. Sven Schewe. From parity and payoff games to linear programming. In Mathematical foundations of computer science 2009, volume 5734 of Lecture Notes in Comput. Sci., pages 675-686. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-03816-7_57.
  34. Oleg Viro. Patchworking real algebraic varieties, 2006. URL: http://arxiv.org/abs/math/0611382.
  35. Oleg Viro. Hyperfields for Tropical Geometry I. Hyperfields and dequantization, 2010. URL: http://arxiv.org/abs/1006.3034.
  36. Karel Zimmermann. A general separation theorem in extremal algebras. Ekonom.-Mat. Obzor, 13(2):179-201, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact