Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 10 von 42
Zurück zur Trefferliste

Online Bin-Coloring

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-6338
  • We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Sven Krumke, Willem de Paepe, Jörg Rambau, Leen Stougie
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Online Optimization; competitive analysis; lower bounds; randomized algorithms
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
Datum der Erstveröffentlichung:02.04.2001
Schriftenreihe (Bandnummer):ZIB-Report (01-07)
ZIB-Reportnummer:01-07
Verlagspublikation:Appeared in: Proc. of the 9th European Symposium on Algorithms, Springer 2001, LNCS 2161, pp. 74-84
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.