2026-09-08T02:22:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26496 2026-09-05T19:45:22Z ddc:004 open_access

The Dirichlet Mechanism for Rounding with Strong Negative Correlation, with Applications Harris, David G. Li, George Z. Raju, Nitya Valieva, Renata Dirichlet distribution copula weighted completion time online rounding Many optimization and scheduling problems can be abstracted in terms of a bipartite "assignment graph" G = (L ∪ R, E), where the goal is to select exactly one edge for each right-node. For example, a right-node may correspond to a job, and a left-node to a possible machine assignment. A common strategy to solve such problems is to obtain a fractional relaxation x_e for each edge e, and then have each right-node independently select an edge with probability x_e. However, this may cause the left-nodes to become unevenly loaded, leading to suboptimal solutions for some problems. To address this, a number of algorithms for dependent rounding with strong negative correlation have been developed, e.g. Bansal, Srinivasan & Svensson (2021), Im & Shadloo (2020), Im & Li (2023), Harris (2024), Naor, Srinivasan & Wajc (2025). We introduce a new method for this, which we call the Dirichlet mechanism. It is based on having each left-node draw Dirichlet random variables for its edges, and then having each right-node select an edge based on these values. This achieves quantitatively stronger negative correlation than previous algorithms, and is also simpler since it avoids the need for a tie-breaking mechanism. We illustrate the mechanism with improved approximation ratios for two problems. For oblivious online dependent rounding, we achieve a 0.68-approximation which improves upon the previous 0.652-approximation of Naor, Srinivasan & Wajc (2025). For the problem of scheduling jobs on unrelated machines to minimize weighted completion time, we achieve a 1.387-approximation which improves upon the 1.398-approximation of Harris (2024). (A recent algorithm of Li (2025) based on iterated rounding also provides a 1.36-approximation if the weights of each job are independent of machine.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik David G. Harris and George Z. Li and Nitya Raju and Renata Valieva 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.107 urn:nbn:de:0030-drops-264963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.107 eng https://creativecommons.org/licenses/by/4.0/legalcode