Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Duan, R., Garg, J., & Mehlhorn, K. (2016). An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. In R. Krauthgamer (Ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 90-106). Philadelphia, PA: SIAM. doi:10.1137/1.9781611974331.ch7.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-81DD-9 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-002C-8903-7
Genre: Konferenzbeitrag
Latex : An Improved Combinatorial Polynomial Algorithm for the Linear {Arrow}-{Debreu} Market

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Duan, Ran1, Autor           
Garg, Jugal1, Autor           
Mehlhorn, Kurt1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with $n$ agents and integral utilities bounded by $U$, the algorithm runs in $O(n^7 \log^3 (nU))$ time. This improves upon the previously best algorithm of Ye by a factor of $\tOmega(n)$. The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of $\tOmega(n^3)$. The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2015-09-1520162016
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: DuanSODA2016
DOI: 10.1137/1.9781611974331.ch7
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
Veranstaltungsort: Arlington, VA, USA
Start-/Enddatum: 2016-01-10 - 2016-01-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
  Kurztitel : SODA 2016
Genre der Quelle: Konferenzband
 Urheber:
Krauthgamer, Robert1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Philadelphia, PA : SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 90 - 106 Identifikator: ISBN: 978-1-61197-433-1