Advances in Approximation Algorithms and Distributed Computing

The field of approximation algorithms and distributed computing is witnessing significant developments, with a focus on improving the efficiency and scalability of algorithms for various problems. Researchers are exploring new techniques to reduce the computational complexity and message complexity of algorithms, leading to more practical solutions for real-world problems. Notably, there is a growing interest in designing message-optimal algorithms and understanding the trade-offs between message complexity and round complexity. Additionally, researchers are investigating the application of approximation algorithms to solve complex problems in areas like graph optimization and house allocation. Overall, the field is moving towards developing more efficient, scalable, and practical algorithms for a wide range of problems. Noteworthy papers include: The paper on Tight Lower Bound for Multicolor Discrepancy, which improves on the previously known lower bound for k-color discrepancy. The paper on Message Optimality and Message-Time Trade-offs for APSP and Beyond, which presents a message-optimal algorithm for weighted APSP and a smooth trade-off between message complexity and round complexity for unweighted APSP.

Sources

Rack-Aware Minimum Storage Partially Cooperative Regenerating Codes with Small Sub-Packetization

Tight Lower Bound for Multicolor Discrepancy

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Online General Knapsack with Reservation Costs

Online Knapsack Problems with Estimates

Message Optimality and Message-Time Trade-offs for APSP and Beyond

One-way Communication Complexity of Minimum Vertex Cover in General Graphs

The Complexity of Minimum-Envy House Allocation Over Graphs

Built with on top of