This study presents a polynomial time algorithm to solve the lossless battery charging problem. In this problem the optimal charging and discharging schedules are chosen to maximize total profit. Traditional solution approaches have relied on either approximations or exponential algorithms. By studying the optimality conditions of this problem, we are able to reduce it to a shortest path problem on acyclic graphs.

## Article

View A Polynomial Algorithm for the Lossless Battery Charging Problem