Constructing Lattice-Free Gradient Polyhedra in Dimension Two

Autor: Joseph Paat, Miriam Schlöter, Emily Speakman

Publikováno v: Integer Programming and Combinatorial Optimization ISBN: 9783030457709
IPCO

Lattice-free gradient polyhedra are optimality certificates for mixed integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables. A classic result of Bell, Doignon, and Scarf s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::25fc1d53f10c2202fc33bf7e752ffa60
https://doi.org/10.1007/978-3-030-45771-6_28

The Integrality Number of an Integer Program

Autor: Joseph Paat, Miriam Schlöter, Robert Weismantel

We introduce the integrality number of an integer program (IP) in inequality form. Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::556f9bd31dcad00cd3dd5e69897a5235
http://arxiv.org/abs/1904.06874

Tight bounds for online TSP on the line

Autor: Antje Bjelde, Leen Stougie, Jan Hackfeld, Miriam Schlöter, Julie Meißner, Yann Disser, Maarten Lipmann, Kevin Schewior, Christoph Hansknecht

Publikováno v: ACM-SIAM Symposium on Discrete Algorithms (SODA)
ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 2017, Barcelona, Spain. pp.994-1005, ⟨10.1137/1.9781611974782.63⟩
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 994-1005
STARTPAGE=994;ENDPAGE=1005;TITLE=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
ACM Transactions on Algorithms, 17(1)
ACM Transactions on Algorithms
ACM Transactions on Algorithms, Association for Computing Machinery, 2021, 17 (1), pp.1-58. ⟨10.1145/3422362⟩
ACM Transactions on Algorithms, 2021, 17 (1), pp.1-58. ⟨10.1145/3422362⟩
ACM Transactions on Algorithms, 17(1):3, 1-58. Association for Computing Machinery (ACM)
Bjelde, A, Disser, Y, Hackfeld, J, Hansknecht, C, Lippmann, M, Meissner, J, Schewior, K, Schloter, M & Stougie, L 2017, Tight Bounds for Online TSP on the Line . in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . ACM, pp. 994-1005 . https://doi.org/10.1137/1.9781611974782.63
Bjelde, A, Hackfeld, J, Disser, Y, Hansknecht, C, Lipmann, M, Meißner, J, Schlöter, M, Schewior, K & Stougie, L 2021, ' Tight Bounds for Online TSP on the Line ', ACM Transactions on Algorithms, vol. 17, no. 1, 3, pp. 1-58 . https://doi.org/10.1145/3422362

We consider the online traveling salesperson problem (TSP), where requests appear online over time on the real line and need to be visited by a server initially located at the origin. We distinguish between closed and open online TSP, depending on wh

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dbb0b01a7b9df55ef71374d5bb43eb1b
https://ir.cwi.nl/pub/26449