Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with dynamic programming:
TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

The Max-Bisection and Min-Bisection are the problems of finding
partitions of the vertices of a given graph into two equal size subsets so as
to maximize or minimize, respectively, the number of edges with exactly one
endpoint in each subset.
In this paper we design the first ... more >>>

TR01-084 | 1st October 2001
Gerhard J. Woeginger

When does a dynamic programming formulation guarantee the existence of an FPTAS?

We derive results of the following flavor:
If a combinatorial optimization problem can be formulated via a dynamic
program of a certain structure and if the involved cost and transition
functions satisfy certain arithmetical and structural conditions, then
the optimization problem automatically possesses a fully polynomial time
approximation scheme (FPTAS).

... more >>>

TR12-041 | 17th April 2012
Stasys Jukna

Limitations of Incremental Dynamic Programs

Revisions: 1

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>

TR14-080 | 11th June 2014
Stasys Jukna

Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

TR15-127 | 7th August 2015
Stasys Jukna, Georg Schnitger

On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm

Revisions: 1

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>>

TR18-042 | 1st March 2018
Stasys Jukna

Incremental versus Non-Incremental Dynamic Programming

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>>

TR18-051 | 15th March 2018
Stasys Jukna

Derandomizing Dynamic Programming and Beyond

Revisions: 1

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>>

TR18-127 | 9th July 2018
Stasys Jukna, Hannes Seiwert

Approximation Limitations of Tropical Circuits

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 ... more >>>

TR19-158 | 11th November 2019
Stasys Jukna, Hannes Seiwert

Sorting Can Exponentially Speed Up Pure Dynamic Programming

Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are ``pure'' in that they only perform basic operations, as $\min$, $\max$, $+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any ... more >>>

TR20-178 | 30th November 2020
Stasys Jukna, Hannes Seiwert, Igor Sergeev

Reciprocal Inputs in Arithmetic and Tropical Circuits

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... more >>>

ISSN 1433-8092 | Imprint