Advances in Online Algorithms and Game Theory

The field of online algorithms and game theory is witnessing significant developments, with a growing focus on improving competitive ratios and efficient algorithms for various problems. Researchers are exploring new techniques to tackle complex challenges, such as online allocation, bipartite matching, and derandomization. Notably, there is a push towards achieving work-efficient and optimal solutions, as seen in the development of parallel derandomization techniques and improvements in online contention resolution schemes. Additionally, the study of dynamic and stochastic settings is gaining traction, with efforts to design efficient algorithms for approximate maximum matching and online stochastic matching.

Some noteworthy papers in this area include: The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization, which presents improved algorithms for $p$-mean welfare maximization. A New Impossibility Result for Online Bipartite Matching Problems, which establishes a new upper bound on the competitive ratio for online bipartite matching. Towards True Work-Efficiency in Parallel Derandomization, which introduces a generic parallel derandomization technique that achieves near-optimal work-efficiency for various problems.

Sources

The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization

A New Impossibility Result for Online Bipartite Matching Problems

Sensor Scheduling in Intrusion Detection Games with Uncertain Payoffs

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set

Universal Online Contention Resolution with Preselected Order

Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model

Edge-weighted Online Stochastic Matching Under Jaillet-Lu LP

Built with on top of