Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Approximating Maximum Integral Multiflows on Bounded Genus Graphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:10:41Z
dc.abstract.enWe devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
dc.affiliationUniwersytet Warszawski
dc.conference.countryWielka Brytania
dc.conference.datefinish2021-07-16
dc.conference.datestart2021-07-12
dc.conference.placeGlasgow
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2021
dc.conference.weblinkhttp://easyconferences.eu/icalp2021/
dc.contributor.authorClaire, Mathieu
dc.contributor.authorMari, Mathieu
dc.contributor.authorJens, Vygen
dc.contributor.authorChien-Chung, Huang
dc.date.accessioned2024-01-24T16:55:14Z
dc.date.available2024-01-24T16:55:14Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.ICALP.2021.80
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/101050
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2021/14149/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages80:1--80:18
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleApproximating Maximum Integral Multiflows on Bounded Genus Graphs
dc.typeJournalArticle
dspace.entity.typePublication