Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Maximum Network Flow with Floating Point Arithmetic

Althaus, E., & Mehlhorn, K. (1998). Maximum Network Flow with Floating Point Arithmetic. Information Processing Letters, 66, 109-113.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Mehlhorn132.pdf (Verlagsversion), 475KB
 
Datei-Permalink:
-
Name:
Mehlhorn132.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Althaus, Ernst1, Autor           
Mehlhorn, Kurt1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We discuss the implementation of network flow algorithms in floating point arithmetic. We give an example to illustrate the difficulties that may arise when floating point arithmetic is used without care. We describe an iterative improvement scheme that can be put around any network flow algorithm for integer capacities. The scheme carefully scales the capacities such that all integers arising can be handled exactly using floating point arithmetic. Let n and m be the number of nodes and edges of the network, respectively. For m 109 and with double precision floating point arithmetic, the number of iterations is always bounded by three, and the relative error in the flow value is at most 2−19. For m 106 and with double precision arithmetic, the relative error after the first iteration is bounded by 10−3.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-01-041998
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 344425
Anderer: Local-ID: C1256428004B93B8-529C02DB1FD42F47C125666000312F2A-althaus-mehlhorn98
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information Processing Letters
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 66 Artikelnummer: - Start- / Endseite: 109 - 113 Identifikator: ISSN: 0020-0190