Publikationer från Malmö universitet
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Improving Online Bin Covering with Little Advice
Univ Ljubljana, Ljubljana, Slovenia; Univ Primorska, Koper, Slovenia.
Malmö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).ORCID-id: 0000-0002-1342-8618
Univ Ljubljana, Ljubljana, Slovenia; Complex Sci Hub, Vienna, Austria.
2024 (engelsk)Inngår i: Combinatorial Algorithms, IWOCA 2024 / [ed] Rescigno, AA; Vaccaro, U, Springer, 2024, Vol. 14764, s. 69-81Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Springer, 2024. Vol. 14764, s. 69-81
Serie
Lecture Notes in Computer Science, ISSN 0302-9743
Emneord [en]
Bin covering, Online computation, Competitive analysis, Advice complexity
HSV kategori
Identifikatorer
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 (tryckt)ISBN: 978-3-031-63021-7 (digital)OAI: oai:DiVA.org:mau-71699DiVA, id: diva2:1907236
Konferanse
35th International Workshop on Combinatorial Algorithms (IWOCA), JUL 01-03, 2024, Ischia, ITALY
Tilgjengelig fra: 2024-10-22 Laget: 2024-10-22 Sist oppdatert: 2026-07-22bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Nilsson, Bengt J.

Søk i DiVA

Av forfatter/redaktør
Nilsson, Bengt J.
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 145 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf