Approximating the Nash Social Welfare with Indivisible Items
From MaRDI portal
Publication:2941527
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)
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
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