1 citations · 2 across the 5 of their papers we have counts for
4 papers · 1 filter
The Incremental Knapsack Problem with Monotone Submodular All-or-Nothing Profits
Federico D'Onofrio, Yuri Faenza, Lingyi Zhang
We study incremental knapsack problems with profits given by a special class of monotone submodular functions, that we dub all-or-nothing. We show that these problems are not harde…
Selectable Heaps and Optimal Lazy Search Trees
Bryce Sandlund, Lingyi Zhang
We show the time extract minimum function of efficient priority queues can be generalized to the extraction of the smallest elements in time (we de…
Approximation Algorithms for The Generalized Incremental Knapsack Problem
Yuri Faenza, Danny Segev, Lingyi Zhang
We introduce and study a discrete multi-period extension of the classical knapsack problem, dubbed generalized incremental knapsack. In this setting, we are given a set of item…
Dynamic Optimality Refuted -- For Tournament Heaps
J. Ian Munro, Richard Peng, Sebastian Wild +1
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys st…