Lagrangian RelaxationThe Cleaning Robot Puzzle: A Price on Every Move
With a battery of five moves, Part 2's robot collects 14 units of dirt and the best route collects 16. A price of 3¼ units of dirt per move proves that no route collects more than 17, and a concave hull shows why no …