A polyhedral perspective on tropical convolutions

DOI10.1007/978-3-031-34347-6_10MaRDI QIDQ6182896

Alexandra Lassota, Cornelius Brand, Martin Koutecký

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Necklaces, convolutions, and \(X+Y\)
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Expressing combinatorial optimization problems by linear programs
• Fast algorithms for the maximum convolution problem
• Which problems have strongly exponential complexity?
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Clustered Integer 3SUM via Additive Combinatorics
• Mathematical Programming and the Maximum Transform
• Polyhedral Characterization of Discrete Dynamic Programming
• Faster All-Pairs Shortest Paths via Circuit Complexity
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• On Problems Equivalent to (min,+)-Convolution
• The Matching Polytope has Exponential Extension Complexity