Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-127 | 9th July 2018 11:09

Approximation Limitations of Tropical Circuits

RSS-Feed




TR18-127
Authors: Stasys Jukna, Hannes Seiwert
Publication: 9th July 2018 12:06
Downloads: 256
Keywords: 


Abstract:

We develop general lower bound arguments for approximating tropical
(min,+) and (max,+) circuits, and use them to prove the
first non-trivial, even super-polynomial, lower bounds on the size
of such circuits approximating some explicit optimization
problems. In particular, these bounds show that the approximation
powers of pure dynamic programming algorithms and greedy algorithms
are incomparable.



ISSN 1433-8092 | Imprint