Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Approximation Hierarchies for the cone of flow matrices

  • Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where $1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$. Several combinatorial problems reduce to a linear optimization problem over $K$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of $K$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities.
Author:Guillaume Sagnol, Marco Blanco, Thibaut Sauvage
Document Type:In Proceedings
Parent Title (English):INOC 2017 – 8th International Network Optimization Conference
First Page:275
Last Page:284
Series:Electronic Notes in Discrete Mathematics
Year of first publication:2018
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.