Second-order methods for distributed approximate single- and multicommodity flow

S. Muthukrishnan, Torsten Suel

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We study local-control algorithms for maximum flow and multicommodity flow problems in distributed networks. We propose a second-order method for accelerating the convergence of the “first-order” distributed algorithms recently proposed by Awerbuch and Leighton. Our experimental study shows that second-order methods are significantly faster than the first-order methods for approximate single- and multicommodity flow problems. Furthermore, our experimental study gives valuable insights into the diffusive processes that underly these local-control algorithms; this leads us to identify many open technical problems for theoretical study.

    Original languageEnglish (US)
    Title of host publicationRandomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings
    EditorsMaria Serna, José D.P Rolim, Michael Luby
    PublisherSpringer Verlag
    Pages369-384
    Number of pages16
    ISBN (Print)354065142X, 9783540651420
    DOIs
    StatePublished - 1998
    Event2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998 - Barcelona, Spain
    Duration: Oct 8 1998Oct 10 1998

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1518
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998
    CountrySpain
    CityBarcelona
    Period10/8/9810/10/98

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Second-order methods for distributed approximate single- and multicommodity flow'. Together they form a unique fingerprint.

    Cite this