Online Knapsack with Frequency Predictions
There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms. In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Competitive Algorithms for Online Knapsack with Succinct Predictions
In the online knapsack problem, the goal is to pack items arriving online with different values and weights into a capacity-limited knapsack to maximize the total value of the accepted items. We study \textit{learning-au…
PredictionHigh-dimensional Linear Bandits with Knapsacks
We study the contextual bandits with knapsack (CBwK) problem under the high-dimensional setting where the dimension of the feature is large. The reward of pulling each arm equals the multiplication of a sparse high-dimen…
Multi-Armed BanditsSingle- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints
Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. Recent results in the area of runtime analysis have pointed out that algorithms such as the (1+1)~EA and Global SEMO can…
DiversityEvolutionary AlgorithmsKnapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization
We study the problem of predicting a set or list of options under knapsack constraint. The quality of such lists are evaluated by a submodular reward function that measures both quality and diversity. Similar to DAgger (…
DiversityDocument SummarizationMulti-Document SummarizationAutomated Composition of Agents: A Knapsack Approach for Agentic Component Selection
Designing effective agentic systems requires the seamless composition and integration of agents, tools, and models within dynamic and uncertain environments. Most existing methods rely on static, semantic retrieval appro…
Semantic Retrieval