{
"@context": "http://schema.org",
"@type": "ScholarlyArticle",
"@id": "https://doi.org/10.4230/lipics.stacs.2011.129",
"identifier": {
"@type": "PropertyValue",
"propertyID": "DOI",
"value": "https://doi.org/10.4230/lipics.stacs.2011.129"
},
"url": "http://drops.dagstuhl.de/opus/volltexte/2011/3005/",
"additionalType": "ConferencePaper",
"name": "Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing",
"author": [
{
"name": "Petr Kolman",
"givenName": "Petr",
"familyName": "Kolman",
"@type": "Person"
},
{
"name": "Christian Scheideler",
"givenName": "Christian",
"familyName": "Scheideler",
"@type": "Person"
}
],
"editor": {
"name": "Marc Herbstritt",
"givenName": "Marc",
"familyName": "Herbstritt",
"contributorType": "Editor",
"@type": "Person"
},
"description": "An elementary h-route flow, for an integer h >= 1, is a set of h edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an h-route flow is a non-negative linear combination of elementary h-route flows. An h-route cut is a set of edges whose removal decreases the maximum h-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of this paper is an approximate duality theorem for multicommodity\n$h$-route cuts and flows, for h <= 3: The size of a minimum h-route cut is at least f/h and at most O(log^3(k)f) where f is the size of the maximum h-route flow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problem for h=3 that has an approximation ratio of O(log^3 k). Previously, polylogarithmic approximation was known only for $h$-route cuts for h <= 2.\nA key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity flows and cuts. Similar results are shown also for the sparsest multiroute cut problem.",
"keywords": "Computer Science, 000 Computer science, knowledge, general works",
"inLanguage": "eng",
"contentSize": "12 pages",
"encodingFormat": "application/pdf",
"datePublished": "2011",
"schemaVersion": "http://datacite.org/schema/kernel-2.1",
"publisher": {
"@type": "Organization",
"name": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany"
}
}