POMACS · 2020
Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging
Proceedings of the ACM on Measurement and Analysis of Computing Systems
How should limited resources be allocated to requests arriving online?
A general fractional multiple knapsack model captures assignment and rate constraints. An online primal dual algorithm obtains near optimal competitive guarantees and is evaluated using charging traces. This work provides an online allocation foundation without requiring learned predictions.
Research themes
Cite this paper
Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, Danny H. K. Tsang. Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2020. https://doi.org/10.1145/3428336
BibTeX
@article{tongxin-online-knapsack,
title = {{Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging}},
author = {Bo Sun and Ali Zeynali and Tongxin Li and Mohammad Hajiesmaili and Adam Wierman and Danny H. K. Tsang},
year = {2020},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
url = {https://doi.org/10.1145/3428336},
doi = {10.1145/3428336}
}
Other versions
Related papers
Counterfactual load forecasting with LLM-structured events and representation learning
NACF turns news into structured treatments and estimates load trajectories under alternative event conditions. Reweighting and representation balancing address observed confounding. Experiments examine factual accuracy and interpretable demand perturbations without claiming that unobserved counterfactual outcomes can be directly validated.
Energy Injection Identification enabled Disaggregation with Deep Multi-Task Learning
DualNILM jointly recognizes appliance states and identifies energy injected behind the meter. Its transformer architecture combines temporal learning tasks to separate consumption from injections, with evaluation on measured and synthesized datasets.
Leveraging Machine-Learned Advice in Strategic Interactions with No-Regret Learners
A measure of advice quality connects simulators and payoff predictions to strategic performance. The paper establishes benefits of reliable advice for approximate Stackelberg play and limitations on simultaneously exploiting accurate advice and protecting against inaccurate advice.