About: Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dl.acm.org/citation.cfm?id=2095180
Description	Given an integer $h$, a graph $G=(V,E)$ with arbitrary positive edge capacities and $k$ pairs of vertices $(s_1,t_1), (s_2,t_2), \ldots, (s_k,t_k)$, called terminals, an $h$-route cut is a set $F\subseteq E$ of edges such that after the removal of the edges in $F$ no pair $s_i-t_i$ is connected by $h$ edge-disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V,E\setminus F)$). The $h$-route cut is a natural generalization of the classical cut problem for multicommodity flows (take $h=1$). The main result of this paper is an $O(h^5 2^{2h} (h+\log k)^2)$-approximation algorithm for the minimum $h$-route cut problem in the case that $s_1=s_2=\cdots=s_k$, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems. Given an integer $h$, a graph $G=(V,E)$ with arbitrary positive edge capacities and $k$ pairs of vertices $(s_1,t_1), (s_2,t_2), \ldots, (s_k,t_k)$, called terminals, an $h$-route cut is a set $F\subseteq E$ of edges such that after the removal of the edges in $F$ no pair $s_i-t_i$ is connected by $h$ edge-disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V,E\setminus F)$). The $h$-route cut is a natural generalization of the classical cut problem for multicommodity flows (take $h=1$). The main result of this paper is an $O(h^5 2^{2h} (h+\log k)^2)$-approximation algorithm for the minimum $h$-route cut problem in the case that $s_1=s_2=\cdots=s_k$, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems. (en)
Title	Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case (en)
skos:prefLabel	Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case (en)
skos:notation	RIV/00216208:11320/12:10129396!RIV13-GA0-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0545), P(GA201/09/0197)
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Kolman, Petr
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	123480
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/12:10129396
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	approximation algorithms; graph; cut; flow; Duality (en)
http://linked.open.../riv/klicoveSlovo	approximation algorithms graph Duality flow cut
http://linked.open...ontrolniKodProRIV	[7CFDEC0AF09A]
http://linked.open...v/mistoKonaniAkce	Japonsko, Kjoto
http://linked.open...i/riv/mistoVydani	USA
http://linked.open...i/riv/nazevZdroje	Proc. of 23 ACM-SIAM Symposium on Discrete Algorithms
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Graph colorings and flows: structure and applications
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Kolman, Petr Scheideler, Christian
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2012-01-17 (xsd:date)
issn	2160-1445
number of pages	11 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Society for Industrial and Applied Mathematics.
https://schema.org/isbn	978-1-61197-211-5
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software