Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Approximation Schemes for Packing Splittable Items with Cardinality Constraints

Epstein, L., & van Stee, R. (2008). Approximation Schemes for Packing Splittable Items with Cardinality Constraints. In C. Kaklamanis, & M. Skutella (Eds.), Approximation and Online Algorithms (pp. 232-245). Berlin: Springer. doi:10.1007/978-3-540-77918-6.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1B0B-E Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-F333-8
Genre: Konferenzbeitrag

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 continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of items must be packed into as few bins as possible. Items may be split, but each bin may contain at most $k$ (parts of) items, where $k$ is some fixed constant. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. We close this problem by providing a polynomial-time approximation scheme for it. We first present a scheme for the case $k=2$ and then for the general case of constant $k$. Additionally, we present \emph{dual} approximation schemes for $k=2$ and constant $k$. Thus we show that for any $\varepsilon>0$, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size $1+\varepsilon$.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2009-03-0320082008
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 428065
DOI: 10.1007/978-3-540-77918-6
URI: http://www.springerlink.com/content/t27t314840n32521/fulltext.pdf
Anderer: Local-ID: C125756E0038A185-4BF479C08756F3CBC125753C0045AA08-vanStee2008j
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 5th International Workshop on Approximation and Online Algorithms
Veranstaltungsort: Eilat, Israel
Start-/Enddatum: 2007-10-11 - 2007-10-12

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Approximation and Online Algorithms
  Kurztitel : WAOA 2007
  Untertitel : 5th International Workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers
Genre der Quelle: Konferenzband
 Urheber:
Kaklamanis, Christos1, Herausgeber
Skutella, Martin2, Herausgeber           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 232 - 245 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 4927 Artikelnummer: - Start- / Endseite: - Identifikator: ISSN: 0302-9743