Tropical Circuit Complexity Limits of Pure Dynamic Programming

This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems. In DP, an optimization problem is broken...

Full description

Bibliographic Details
Main Author: Jukna, Stasys
Format: eBook
Language:English
Published: Cham Springer International Publishing 2023, 2023
Edition:1st ed. 2023
Series:SpringerBriefs in Mathematics
Subjects:
Online Access:
Collection: Springer eBooks 2005- - Collection details see MPG.ReNa
LEADER 02633nmm a2200349 u 4500
001 EB002187995
003 EBX01000000000000001325480
005 00000000000000.0
007 cr|||||||||||||||||||||
008 231206 ||| eng
020 |a 9783031423543 
100 1 |a Jukna, Stasys 
245 0 0 |a Tropical Circuit Complexity  |h Elektronische Ressource  |b Limits of Pure Dynamic Programming  |c by Stasys Jukna 
250 |a 1st ed. 2023 
260 |a Cham  |b Springer International Publishing  |c 2023, 2023 
300 |a IX, 129 p. 19 illus  |b online resource 
505 0 |a Chapter. 1. Basics -- Chapter. 2. Combinatorial Bounds -- Chapter. 3. Rectangle Bounds -- Chapter. 4. Bounds for Approximating Circuits -- Chapter. 5. Tropical Branching Programs -- Chapter. 6. Extended Tropical Circuits 
653 |a Computer science / Mathematics 
653 |a Discrete Optimization 
653 |a Mathematical Applications in Computer Science 
653 |a Computational complexity 
653 |a Discrete Mathematics 
653 |a Discrete mathematics 
653 |a Mathematical optimization 
653 |a Computational Complexity 
041 0 7 |a eng  |2 ISO 639-2 
989 |b Springer  |a Springer eBooks 2005- 
490 0 |a SpringerBriefs in Mathematics 
028 5 0 |a 10.1007/978-3-031-42354-3 
856 4 0 |u https://doi.org/10.1007/978-3-031-42354-3?nosfx=y  |x Verlag  |3 Volltext 
082 0 |a 511.1 
520 |a This book presents an enticing introduction to tropical circuits and their use as a rigorous mathematical model for dynamic programming (DP), which is one of the most fundamental algorithmic paradigms for solving combinatorial, discrete optimization problems. In DP, an optimization problem is broken up into smaller subproblems that are solved recursively. Many classical DP algorithms are pure in that they only use the basic (min,+) or (max,+) operations in their recursion equations. In tropical circuits, these operations are used as gates. Thanks to the rigorous combinatorial nature of tropical circuits, elements from the Boolean and arithmetic circuit complexity can be used to obtain lower bounds for tropical circuits, which play a crucial role in understanding the limitations and capabilities of these computational models. This book aims to offer a toolbox for proving lower bounds on the size of tropical circuits. In this work, the reader will find lower-bound ideas and methods that have emerged in the last few years, with detailed proofs. Largely self-contained, this book is meant to be approachable by graduate students in mathematics and computer science with a special interest in circuit complexity