Flows with Unit Path Capacities and Related Packing and Covering Problems
| dc.contributor.author | Martens, Maren | |
| dc.contributor.author | Skutella, Martin | |
| dc.date.accessioned | 2021-12-17T10:07:54Z | |
| dc.date.available | 2021-12-17T10:07:54Z | |
| dc.date.issued | 2008 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15639 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14412 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | network flows | en |
| dc.subject.other | packing | en |
| dc.subject.other | covering | en |
| dc.subject.other | approximation | en |
| dc.title | Flows with Unit Path Capacities and Related Packing and Covering Problems | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2008, 21 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1