Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Improved Results for a Memory Allocation Problem

Epstein, L., & van Stee, R. (2011). Improved Results for a Memory Allocation Problem. Theory of Computing Systems, 48(1), 79-92. doi:10.1007/s00224-009-9226-2.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-123E-E Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-0565-1
Genre: Zeitschriftenartikel

Dateien

einblenden: Dateien
ausblenden: Dateien
:
splitemj9.pdf (beliebiger Volltext), 115KB
 
Datei-Permalink:
-
Name:
splitemj9.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
© The Author(s) 2009
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Epstein, Leah1, Autor
van Stee, Rob2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. This problem was recently introduced by Chung et al.~\cite{ChGrVM06}. We give a simple $\frac 32$-approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most $k$ parts of items. We show that this general case is strongly NP-hard for any $k \geq 3$. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily close to $\frac 75$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20112011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 618646
DOI: 10.1007/s00224-009-9226-2
URI: http://dx.doi.org/10.1007/s00224-009-9226-2
Anderer: Local-ID: C1256428004B93B8-D4285FA8B979BEB2C12577F4004E594F-EpsSte11
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Theory of Computing Systems
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, NY : Springer
Seiten: - Band / Heft: 48 (1) Artikelnummer: - Start- / Endseite: 79 - 92 Identifikator: ISSN: 1432-4350