4 papers
Online Geometric Packing through Online TSP Scheduling
Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae +3
We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles…
Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models
Kailash Gopal Darmasubramanian, Akash Pareek, Arindam Khan +1
Optimizing the timing and frequency of ads is a central problem in digital advertising, with significant economic consequences. Existing scheduling policies rely on simple heuristi…
Near-optimal Algorithms for Stochastic Online Bin Packing
Nikhil Ayyadevara, Rajni Dabas, Arindam Khan +1
We study the online bin packing problem under two stochastic settings. In the bin packing problem, we are given n items with sizes in (0,1] and the goal is to pack them into the mi…
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Pritam Acharya, Sujoy Bhore, Aaryan Gupta +3
We study the geometric knapsack problem in which we are given a set of -dimensional objects (each with associated profits) and the goal is to find the maximum profit subset that…