Record link: 
http://hdl.handle.net/20.500.12708/188932
-
Title: 
A Polyhedral Perspective on Tropical Convolutions
en
Citation: 
Brand, C., Koutecký, M., & Lassota, A. (2023). A Polyhedral Perspective on Tropical Convolutions. In S.-Y. Hsieh, L.-J. Hung, & C.-W. Lee (Eds.), Combinatorial Algorithms : 34th International Workshop, IWOCA 2023, Tainan, Taiwan, June 7–10, 2023, Proceedings (pp. 111–122). Springer. https://doi.org/10.1007/978-3-031-34347-6_10
-
Publisher DOI: 
10.1007/978-3-031-34347-6_10
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Brand, Cornelius 
Koutecký, Martin 
Lassota, Alexandra 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Combinatorial Algorithms : 34th International Workshop, IWOCA 2023, Tainan, Taiwan, June 7–10, 2023, Proceedings 
-
ISBN: 
978-3-031-34346-9
-
Volume: 
13889
-
Date (published): 
2023
-
Event name: 
Combinatorial Algorithms - 34th International Workshop, IWOCA 2023 
en
Event date: 
7-Jun-2023 - 10-Jun-2023
-
Event place: 
Tainan, Taiwan (Province of China)
-
Number of Pages: 
12
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Tropical Convolutions; Exact Algorithms; Computational Complexity
en
Abstract: 
Tropical (or min-plus) convolution is a well-studied algorithmic primitive in fine-grained complexity. We exhibit a novel connection between polyhedral formulations and tropical convolution, through which we arrive at a dual variant of tropical convolution. We show this dual operation to be equivalent to primal convolutions. This leads us to considering the geometric objects that arise from dual tropical convolution as a new approach to algorithms and lower bounds for tropical convolutions. In particular, we initiate the study of their extended formulations.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

218
checked on Nov 23, 2023

Google ScholarTM

Check