Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Improving Online Bin Covering with Little Advice
Univ Ljubljana, Ljubljana, Slovenia; Univ Primorska, Koper, Slovenia.
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-1342-8618
Univ Ljubljana, Ljubljana, Slovenia; Complex Sci Hub, Vienna, Austria.
2024 (English)In: Combinatorial Algorithms, IWOCA 2024 / [ed] Rescigno, AA; Vaccaro, U, Springer, 2024, Vol. 14764, p. 69-81Conference paper, Published paper (Refereed)
Abstract [en]

The online bin covering problem is: given an input sequence of items find a placement of the items in the maximum number of bins such that the sum of the items' sizes in each bin is at least 1. Boyar et al. [3] present a strategy that with O(log log n) bits of advice, where n is the length of the input sequence, achieves a competitive ratio of 8/15 approximate to 0.5333 ... . We show that with a strengthened analysis and some minor improvements, the same strategy achieves the significantly improved competitive ratio of 135/242 approximate to 0.5578 ... , still using O(log log n) bits of advice.

Place, publisher, year, edition, pages
Springer, 2024. Vol. 14764, p. 69-81
Series
Lecture Notes in Computer Science, ISSN 0302-9743
Keywords [en]
Bin covering, Online computation, Competitive analysis, Advice complexity
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-71699DOI: 10.1007/978-3-031-63021-7_6ISI: 001282050500006ISBN: 978-3-031-63020-0 (print)ISBN: 978-3-031-63021-7 (electronic)OAI: oai:DiVA.org:mau-71699DiVA, id: diva2:1907236
Conference
35th International Workshop on Combinatorial Algorithms (IWOCA), JUL 01-03, 2024, Ischia, ITALY
Available from: 2024-10-22 Created: 2024-10-22 Last updated: 2024-10-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Nilsson, Bengt J.

Search in DiVA

By author/editor
Nilsson, Bengt J.
By organisation
Department of Computer Science and Media Technology (DVMT)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 101 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf