2023/09/24 by Andrej Brodnik, Brodnik, Andrej, Bengt J. Nilsson +3
Computer Science · Decision Sciences · #Algorithms and Data Compression #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2309.13647
openalex publication_date 2023/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show an asymptotic 2/3-competitive strategy for the bin covering problem using O(b+log n) bits of advice, where b is the number of bits used to encode a rational value and n is the length of the input sequence.