12 problems

Robust flow gap conjecture. For any $\Gamma\in\mathbb{N}$, the inequalities

Loose weighted-web conjecture. A loose weighted web is linkable.

Morell and Skutella's conjecture. Any fractional flow $(x_e)_{e\in E}$ can be expressed as a convex combination of unsplittable flows $(y_e)_{e\in E}$ satisfying both bounds. The s…

Goemans' conjecture. Every fractional flow $(x_e)_{e\in E}$ can be expressed as a convex combination of unsplittable flows $(y_e)_{e\in E}$ satisfying these bounds. This is equival…

Let $S$ be a source set in the directed hypercube with separation distance $r$. Consider a flow network with unit edge capacities and vertex capacities $r^2$. Flow-capacity conject…

Let $(E,\mathcal{P})$ be an abstract network. Suppose there is a combinatorial, strongly polynomial algorithm for the abstract shortest $s$-$t$-path problem that accesses…

Consider the classical pattern-based formulation for the cutting-stock problem, viewed as a path-flow model obtained by Dantzig–Wolfe decomposition. Let $z_{lb}$ denote its optimal…

Priority-queue implementation conjecture. Such an algorithm can be implemented with $O(n)$ queries to a priority queue.

Fontes et al.'s conjecture. The actual gap between the solutions obtained by their local-search heuristic for single-source single-commodity concave-cost flow problems and the opti…

Convergence conjecture. The dynamics converge to an element of

Orthogonal web-flow conjecture. In every weighted web there exists a web-flow $f$ and an $A$-$B$ separating set orthogonal to $f$.

Orthogonal-pair conjecture. In any possibly infinite network there exists an orthogonal pair of a flow and a cut.