Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Krzysztof Piecuch

dblp:207/7789 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
0since 2021 · last 2020
—ORCID · unresolved

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Mathematical optimization · 50% Approximation and online algorithms · 33% Algorithmic game theory and mechanism design · 17%

Topics — the 6 heaviest of 6, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Mathematical optimization
discrete optimization
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020
Mathematical optimization › knapsack problem
multiple knapsack
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020
Approximation and online algorithms
online algorithms
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020
Approximation and online algorithms › online algorithms › online packing and covering
online knapsack
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020
Mathematical optimization › combinatorial optimization › packing problems
online packing
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020
Algorithmic game theory and mechanism design
resource allocation
0.412020
An Optimal Algorithm for Online Multiple Knapsack · ICALP 2020

Methods — techniques the papers use, named apart from their topics

deterministic algorithm · 0.4competitive ratio analysis · 0.4
YearPublicationVenuePosition
2020 An Optimal Algorithm for Online Multiple Knapsack
abstract
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of n bins (knapsacks) of equal size. The gain of an algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the 0.5-competitive algorithm FirstFit (the result holds for any n ≥ 2). We present the first algorithm that beats this ratio, achieving the competitive ratio of 1/(1+ln(2))-O(1/n) ≈ 0.5906 - O(1/n). Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of 1/(1+ln(2)) for randomized solutions was given previously by Cygan et al. [TOCS 2016].
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
ICALP3