Advances in Graph Algorithms and Online Problems

The field of graph algorithms and online problems is witnessing significant developments, with a focus on improving the efficiency and competitiveness of algorithms in various settings. Researchers are exploring new techniques and models to tackle complex problems, such as online firefighting and bipartite matching, and are making progress in understanding the limitations and possibilities of different approaches. Notably, the study of popular matchings and proportional allocations is leading to a deeper understanding of the underlying structures and relationships in graphs. Overall, the field is moving towards a more nuanced understanding of the interplay between algorithmic design, graph structure, and competitive analysis. Noteworthy papers include: The paper on online firefighting on cactus graphs, which proposes an O(√n)-competitive algorithm and studies the impact of cycles on the problem's complexity. The paper on the popular dimension of matchings, which provides tight bounds on the popular dimension in various settings and sheds light on the existence and properties of popular matchings.

Sources

Orientation does not help with 3-coloring a grid in online-LOCAL

Online Firefighting on Cactus Graphs

The Popular Dimension of Matchings

Degree-bounded Online Bipartite Matching: OCS vs. Ranking

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations

Built with on top of