Advances in Allocation and Optimization

The field of allocation and optimization is witnessing significant developments, with a focus on improving the efficiency and fairness of various allocation mechanisms. Researchers are exploring new techniques to enhance the performance of existing algorithms, such as those used in contract design, bin covering, and inventory staggering. Notably, the improvement of approximation guarantees for various problems, including the subadditive maximin share problem and the inventory staggering problem, is a key area of research. Furthermore, the development of novel mechanisms, such as those for facility location and multigraphs, is also underway.

Some notable papers in this area include: Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem, which improves the bound for subadditive agents to a 1/O((log log n)^2)-MMS guarantee. New Approximation Guarantees for The Inventory Staggering Problem, which devises algorithmic techniques to surpass existing approximation guarantees for the inventory staggering problem.

Sources

Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem

Multi-Project Contracts

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem

Longer Lists Yield Better Matchings

Improving Online Bin Covering with Little Advice

Improved Approximate EFX Guarantees for Multigraphs

New Approximation Guarantees for The Inventory Staggering Problem

Equitable Mechanism Design for Facility Location

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds

Built with on top of