Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Brown, Adam, Laddha, Aditi, Pittu, Madhusudhan Reddy, Singh, Mohit
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

Approximating Nash Social Welfare by Matching and Local Search
by: Garg, Jugal, et al.
Published: (2022)

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

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

Threshold Policies with Tight Guarantees for Online Selection with Convex Costs
by: Tan, Xiaoqi, et al.
Published: (2023)

Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs
by: Vazirani, Vijay V.
Published: (2025)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

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

Non-Exclusive Notifications for Ride-Hailing at Lyft I: Single-Cycle Approximation Algorithms
by: Ekbatani, Farbod, et al.
Published: (2026)

Group Fair Matchings using Convex Cost Functions
by: Panda, Atasi, et al.
Published: (2025)

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)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

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

New Convex Programming Technique for Nash Social Welfare and Scheduling
by: Feng, Yuda, et al.
Published: (2026)

Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings
by: V., Vishwa Prakash H., et al.
Published: (2023)

Best of Both Worlds Guarantees for Equitable Allocations
by: Bhaskar, Umang, et al.
Published: (2025)

The Landscape of Almost Equitable Allocations
by: Hosseini, Hadi, et al.
Published: (2025)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
by: Bowers, Robin, et al.
Published: (2025)

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

Weighted Envy Freeness With Bounded Subsidies
by: Elmalem, Noga Klein, et al.
Published: (2024)

Equitable Colorings of Vertex-Weighted Graphs
by: Barman, Siddharth, et al.
Published: (2026)

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)

The Min Max Average Cycle Weight Problem
by: Elmalem, Noga Klein, et al.
Published: (2025)

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

Fair Rent Division: New Budget and Rent Constraints
by: Gangam, Rohith Reddy, et al.
Published: (2025)

Condorcet Winners and Anscombes Paradox Under Weighted Binary Voting
by: Baharav, Carmel, et al.
Published: (2025)

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
by: Gupta, Sushmita, et al.
Published: (2025)

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

Efficient Approximation Schemes for Stochastic Probing and Selection-Stopping Problems
by: Segev, Danny, et al.
Published: (2020)

Algorithmic Persuasion with Evidence
by: Hoefer, Martin, et al.
Published: (2020)

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

Computing Power Indices in Weighted Majority Games with Formal Power Series
by: Kakimura, Naonori, et al.
Published: (2025)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
by: Andersen, Martin Jupakkal, et al.
Published: (2025)

Improved Parallel Algorithms for EF1 Allocations
by: Gowda, Kishen N, et al.
Published: (2026)