Malmö University Publications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
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: 001282050500006Scopus ID: 2-s2.0-105044385680ISBN: 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: 2026-07-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

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: 145 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