Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14412
For citation please use:
Main Title: Flows with Unit Path Capacities and Related Packing and Covering Problems
Author(s): Martens, Maren
Skutella, Martin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15639
http://dx.doi.org/10.14279/depositonce-14412
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest.
Subject(s): network flows
packing
covering
approximation
Issue Date: 2008
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2008, 21
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-021-2008.pdf
Format: Adobe PDF | Size: 158.11 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.