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.
How might electricity demand change under a different news event? AI for energy electric vehicle charging demand response renewable energy load forecasting decarbonization large language models LLM agents contextual control world models reinforcement learning dueling banditsEnergy 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.
Can appliances be identified when solar and storage obscure meter readings? AI for energy electric vehicle charging demand response renewable energy load forecasting decarbonization information theory graph learning sample complexity compressed sensing graph neural networks Riemannian geometryLeveraging 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.
How useful is imperfect advice against an adaptive opponent? game theory learning in games Bayesian games Stackelberg strategies equity public models learning augmented algorithms algorithms with predictions competitive analysis robustness consistency online optimization