Loading [MathJax]/jax/output/HTML-CSS/jax.js

Notation for Dynamic Programming Algorithms

Here we collect notation related to dyanmic programming algorithms (and the problems they solve).

Subset Sum Problem

Notation	Meaning
$w_1,\dots,w_n$	The set of all $n$ integers (assume $w_i > 0$ for every $i\in [n]$ )
$W$	The total bound/budget $W\ge 0$ .
$S$	A subset $S\subseteq [n]$ , what we should output.
$w(S)$	Weight of $S$ , defined as $\sum_{i\in S} w_i$ . Our goal is to put an $S$ that maximizes $w(S)$ .
$\text{OPT}(j,B)$	Weight of the optimal subset for the numbers $w_1,\dots,w_j$ and budget $B$ .
$M$	An $(W+1)\times (n+1)$ matrix that is computed by the algorithm such that $M[B][j]=\text{OPT}(j,B)$ .

Shortest Path Problem

Notation	Meaning
$c_e$	Given a (directed) graph $G=(V,E)$ where every edge $e\in E$ has a cost $c_e$ (which can be negative).
$t$	Terminal $t\in V$ . The goal is to find the shorest path from every $s\in V$ to $t$ .
Negative cycle	A cycle $C$ such that $\sum_{e\in C} c_e < 0$ . We assume $G$ has no negative cycles.
$\text{OPT}(u,i)$	Cost of shortest $u-t$ path with at most $i$ edges in it. We are interested in $\text{OPT}(s,n-1)$ for every $s\in V$ .