MaxMin allocation via degree lower-bounded arborescences

DOI10.1145/1536414.1536488zbMath1304.91143OpenAlexW2154014787MaRDI QIDQ5172749

MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536488

zbMATH Keywords

linear programminggraphsapproximation algorithmslift-and-project

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Minimax problems in mathematical programming (90C47) Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (25)

Approximating the Nash Social Welfare with Indivisible Items ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Max-Cut Under Graph Constraints ⋮ APX-hardness of maximizing Nash social welfare with indivisible items ⋮ A truthful constant approximation for maximizing the minimum load on related machines ⋮ Parameterized orientable deletion ⋮ Integrality gaps for colorful matchings ⋮ Fair and efficient allocation with few agent types, few item types, or small value levels ⋮ Unnamed Item ⋮ Structural parameters for scheduling with assignment restrictions ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ The efficiency of fair division ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Convex Relaxations and Integrality Gaps ⋮ Approximating graph-constrained max-cut ⋮ Unnamed Item ⋮ An EPTAS for scheduling on unrelated machines of few different types

This page was built for publication: MaxMin allocation via degree lower-bounded arborescences