In briefImproved Randomized Online Matching Beyond 0.55 Competitive Ratio
SummaryThis paper presents a randomized algorithm for edge-weighted online bipartite matching with free disposal, achieving a competitive ratio of 0.556195. This improves on the previous 0.5368 guarantee by Blanc and Charikar. The algorithm builds on online correlated selection and is analyzed with a state-dependent primal-dual method, with some selection inequalities verified by a computer-assisted proof whose verifiers are publicly available. The authors also show that triangular unit-weight inputs asymptotically attain the guarantee of the underlying ideal algorithm, indicating the analysis is tight.
WhyThe authors improve the competitive ratio for edge-weighted online bipartite matching to 0.556 via state-dependent primal-dual analysis with computer-assisted verification and a tight bound.
In briefProphet Secretary for Matroids and XOS Valuations: A Strict Separation at 1-1/e
SummaryThis paper studies online allocation where element values are drawn independently and revealed in random order, with the goal of choosing an independent set or disjoint buyer bundles compared against the expected offline optimum. For matroids, the authors give a randomized algorithm achieving a (1-1/e+10^-6) competitive ratio with polynomial running time in the independence-oracle model. For combinatorial auctions with XOS valuations, they show 1-1/e is the optimal competitive ratio, establishing a strict separation between the two settings.
WhyThe authors show matroid prophet-secretary beats 1-1/e and give a tight 1-1/e bound for XOS auctions, a notable separation result.
In briefStability and Perfection in Constrained Weighted Network Games: Defining and proving existence of stable networks, and their refinements, when agents face capacity and budget limits.
SummaryThe paper introduces a framework for constrained weighted network formation, where agents assign continuous weights to coalitions subject to coalitional capacity and individual budget constraints. It defines a new stability notion, coalitionwise stability, and proves that such stable networks exist under continuity and componentwise quasiconcavity of payoffs. The authors also study perfection-based refinements inspired by Selten and Bich and Teteryatnikova, and show that trembling-hand and perturbative formulations are equivalent under a componentwise monotonicity assumption.
In briefTight bounds for fractional and randomized truthful scheduling
SummaryThis paper studies truthful scheduling on unrelated machines and proves that every deterministic truthful fractional mechanism has worst-case approximation ratio at least (n+1)/2, matching the known upper bound. Because truthful-in-expectation mechanisms induce truthful fractional mechanisms, the same lower bound extends to all truthful-in-expectation and universally truthful mechanisms. The authors also give a universally truthful mechanism with approximation ratio n/2+o(n). Together, the results establish that the optimal leading constant for randomized truthful scheduling is 1/2.
WhyThe authors resolve a longstanding open problem, proving a (n+1)/2 lower bound for truthful fractional scheduling and matching randomized upper bounds asymptotically.
Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias et al.
In briefflash-comm: A communication library that synchronizes data transfers themselves to speed up LLM decoding.
SummaryThe paper presents flash-comm, a communication library for LLM decoding that merges readiness synchronization with data movement. Each data block carries evidence of its own readiness, so receivers can validate needed blocks without separate inter-GPU barriers. On a server with eight NVIDIA B300 GPUs, all-reduce latency fell by a median of 28.8% (up to 43.7%) compared with custom AR v2, and time per output token dropped 1.7-6.8% in end-to-end decoding.
