English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The online knapsack problem is a classic problem in the field of onlinealgorithms. Its canonical version asks how to pack items of different valuesand weights arriving online into a capacity-limited knapsack so as to maximizethe total value of the admitted items. Although optimal competitive algorithmsare known for this problem, they may be fundamentally unfair, i.e., individualitems may be treated inequitably in different ways. Inspired by recentattention to fairness in online settings, we develop a natural andpractically-relevant notion of time fairness for the online knapsack problem,and show that the existing optimal algorithms perform poorly under this metric.We propose a parameterized deterministic algorithm where the parameterprecisely captures the Pareto-optimal trade-off between fairness andcompetitiveness. We show that randomization is theoretically powerful enough tobe simultaneously competitive and fair; however, it does not work well inpractice, using trace-driven experiments. To further improve the trade-offbetween fairness and competitiveness, we develop a fair, robust (competitive),and consistent learning-augmented algorithm with substantial performanceimprovement in trace-driven experiments.

Time Fairness in Online Knapsack Problems