Approximating Nash Social Welfare by Matching and Local Search

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Garg, Jugal, Husić, Edin, Li, Wenzheng, Végh, László A., Vondrák, Jan
Format:	Preprint
Published:	2022
Subjects:	Computer Science and Game Theory Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Correlation Gap of Matroids
by: Husić, Edin, et al.
Published: (2022)

Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
by: Feng, Yuda, et al.
Published: (2024)

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
by: Feng, Yuda, et al.
Published: (2024)

Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps
by: Bei, Xiaohui, et al.
Published: (2025)

Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs
by: Brown, Adam, et al.
Published: (2024)

Improved MMS Approximations for Few Agent Types
by: Garg, Jugal, et al.
Published: (2025)

Approximating Competitive Equilibrium by Nash Welfare
by: Garg, Jugal, et al.
Published: (2024)

Online Nash Welfare Maximization Without Predictions
by: Huang, Zhiyi, et al.
Published: (2022)

A Strongly Polynomial Algorithm for Arctic Auctions
by: Garg, Jugal, et al.
Published: (2026)

Prophet Inequalities with Cancellation Costs
by: Ekbatani, Farbod, et al.
Published: (2024)

Cycle Cancellation for Submodular Fractional Allocations and Applications
by: Chekuri, Chandra, et al.
Published: (2025)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

Beyond the Half-Approximation: Fair and Efficient Online Class Matching
by: Borst, Sander, et al.
Published: (2026)

Tradeoffs in Privacy, Welfare, and Fairness for Facility Location
by: Fish, Sara, et al.
Published: (2026)

Optimally Interpolating between Ex-Ante Fairness and Welfare
by: Høgsgaard, Mikael Møller, et al.
Published: (2023)

The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
by: Huang, Zhiyi, et al.
Published: (2025)

Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare
by: Zargari, Faraz, et al.
Published: (2025)

Prophet Secretary and Matching: the Significance of the Largest Item
by: Chen, Ziyun, et al.
Published: (2024)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Robust Popular Matchings
by: Bullinger, Martin, et al.
Published: (2024)

Stable Matching with Deviators and Conformists
by: Glitzner, Frederik, et al.
Published: (2026)

Matching with Nested and Bundled Pandora Boxes
by: Bowers, Robin, et al.
Published: (2024)

Edge-Weighted Online Bipartite Matching
by: Fahrbach, Matthew, et al.
Published: (2020)

Stable Hypergraph Matching in Unimodular Hypergraphs
by: Biró, Péter, et al.
Published: (2025)

Fairness and Efficiency in Online Class Matching
by: Hajiaghayi, MohammadTaghi, et al.
Published: (2024)

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
by: Ali, Dildar, et al.
Published: (2025)

Logarithmic Approximation for Road Pricing on Grids
by: Constantinescu, Andrei, et al.
Published: (2025)

Truthful Matching with Online Items and Offline Agents
by: Feldman, Michal, et al.
Published: (2022)

Condorcet Dimension and Pareto Optimality for Matchings and Beyond
by: Kavitha, Telikepalli, et al.
Published: (2026)

Near-Feasible Stable Matchings: Incentives and Optimality
by: Glitzner, Frederik
Published: (2026)

Fairness and Efficiency in Two-Sided Matching Markets
by: Jain, Pallavi, et al.
Published: (2025)

Online Matching Meets Sampling Without Replacement
by: Huang, Zhiyi, et al.
Published: (2024)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

A Minimax Perspective on Almost-Stable Matchings
by: Glitzner, Frederik, et al.
Published: (2026)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Optimal Capacity Modification for Stable Matchings with Ties
by: Ranjan, Keshav, et al.
Published: (2024)

MATWA: A Web Toolkit for Matching under Preferences
by: Glitzner, Frederik, et al.
Published: (2024)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
by: Huang, Xin, et al.
Published: (2025)

Optimal Competitive Ratio of Two-sided Online Bipartite Matching
by: Tang, Zhihao Gavin
Published: (2026)

Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
by: McCauley, Samuel, et al.
Published: (2026)