ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Alles auswählen Exportieren

Unbekannt

Approximation Hierarchies for the cone of flow matrices (2018)

Sagnol, Guillaume ; Blanco, Marco ; Sauvage, Thibaut

zur Merkliste hinzufügen auf der Merkliste

Details

Publikationsdatum: 2020-08-05

Beschreibung: 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.

Sprache: Englisch

Materialart: conferenceobject , doc-type:conferenceObject

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

OPUS

Überblick

Treffer 1 - 1 | 1 Treffer