Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12830Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Karakostas, G. | en |
| dc.date.accessioned | 2015-11-24T17:24:00Z | - |
| dc.date.available | 2015-11-24T17:24:00Z | - |
| dc.identifier.issn | 1549-6325 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/12830 | - |
| dc.rights | Default Licence | - |
| dc.subject | multicommodity flows | en |
| dc.subject | fully-polynomial time approximation schemes | en |
| dc.subject | algorithms | en |
| dc.subject | packing | en |
| dc.title | Faster Approximation Schemes for Fractional Multicommodity Flow Problems | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1145/1328911.1328924 | - |
| heal.identifier.secondary | <Go to ISI>://000265816600013 | - |
| heal.identifier.secondary | http://delivery.acm.org/10.1145/1330000/1328924/a13-karakostas.pdf?ip=195.251.197.109&id=1328924&acc=ACTIVE%20SERVICE&key=C2716FEBFA981EF1E9B06A0954DB6E6FB2E80188D446F61C&CFID=286340637&CFTOKEN=12197681&__acm__=1390819474_04620ef789805273b15953c3a347dfbb | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2008 | - |
| heal.abstract | We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. We show that by modifying the algorithms by Garg and Konemann [1998] and Fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from (O) over tilde(epsilon(-2)(m(2)+ km)) to (O) over tilde(epsilon(-2)m(2)) for an implicit representation of the output, or (O) over tilde(epsilon(-2)(m(2)+ kn)) for an explicit representation, where (O) over tilde (f) denotes a quantity that is O(f log(O(1)) m). The implicit representation consists of a set of trees rooted at sources (there can be more than one tree per source), and with sinks as their leaves, together with flow values for the flow directed from the source to the sinks in a particular tree. Given this implicit representation, the approximate value of the concurrent flow is known, but if we want the explicit flow per commodity per edge, we would have to combine all these trees together, and the cost of doing so may be prohibitive. In case we want to calculate explicitly the solution flow, we modify our schemes so that they run in time polylogarithmic in nk (n is the number of nodes in the network). This is within a polylogarithmic factor of the trivial lower bound of time Omega(nk) needed to explicitly write down a multicommodity flow of k commodities in a network of n nodes. Therefore our schemes are within a polylogarithmic factor of the minimum possible dependencies of the running time on the number of commodities k. | en |
| heal.journalName | Acm Transactions on Algorithms | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Karakostas-2008-Faster Approximation.pdf | 241.62 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
