Approximating the Nash Social Welfare with Indivisible Items

DOI10.1145/2746539.2746589zbMath1322.91030MaRDI QIDQ2941527

Vasilis Gkatzelis, Richard John Cole

Publication date: 21 August 2015

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

zbMATH Keywords

geometric meanfair divisionapproximation algorithmsNash bargainingNash productNash social welfare

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Welfare economics (91B15)

Related Items

Approximating the Nash Social Welfare with Indivisible Items ⋮ Approximating Nash social welfare under binary XOS and binary subadditive valuations ⋮ APX-hardness of maximizing Nash social welfare with indivisible items ⋮ Exact solution approaches for integer linear generalized maximum multiplicative programs through the lens of multi-objective optimization ⋮ Approximate competitive equilibrium with generic budget ⋮ Computing fair and efficient allocations with few utility values ⋮ Computing welfare-maximizing fair allocations of indivisible goods ⋮ EFX under budget constraint ⋮ Unnamed Item ⋮ Computing fair and efficient allocations with few utility values ⋮ From Monetary to Nonmonetary Mechanism Design via Artificial Currencies ⋮ Ascending-Price Algorithms for Unknown Markets ⋮ On fair division for indivisible items ⋮ Nash Social Welfare, Matrix Permanent, and Stable Polynomials ⋮ Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item