DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.90

New Convex Programming Technique for Nash Social Welfare and Scheduling

Authors: Yuda Feng, Weijiang Hu, and Shi Li

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We propose a new convex programming relaxation for the weighted Nash social welfare (NSW) problem that achieves a matching (e^{1/e} ≈ 1.445)-approximation via the rounding algorithm of Feng and Li. Unlike the exponential-size configuration LP used in prior work, our formulation can be converted into a compact linear program of polynomial size, incurring only an additive loss of ln(1+ε) in the objective. This allows the program to be solved directly using standard LP solvers, without the ellipsoid method or dual separation oracles. In the unweighted case, we show that our convex program is equivalent to the restricted-spending Fisher market convex program of Cole and Gkatzelis, yielding a constructive proof that its integrality gap is exactly e^{1/e}. With a minor modification, our analysis also gives a simple proof of the e^{1/e} EF1 gap for the identical agent setting. Finally, we show that our convex programming technique extends to two unrelated machine scheduling problems, recovering the best-known approximation ratios with simpler analyses.

Cite as

Yuda Feng, Weijiang Hu, and Shi Li. New Convex Programming Technique for Nash Social Welfare and Scheduling. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 90:1-90:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2026.90,
  author =	{Feng, Yuda and Hu, Weijiang and Li, Shi},
  title =	{{New Convex Programming Technique for Nash Social Welfare and Scheduling}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{90:1--90:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.90},
  URN =		{urn:nbn:de:0030-drops-264797},
  doi =		{10.4230/LIPIcs.ICALP.2026.90},
  annote =	{Keywords: Nash Social Welfare, Convex Programming, Approximation Algorithms, Scheduling}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.63

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

Authors: Yuda Feng and Shi Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e^{1/e} + ε ≈ 1.445 + ε, which matches the best known approximation ratio for the unweighted case [Barman et al., 2018]. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems [Shmoys and Tardos, 1993]. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most e^{1/e} ≈ 1.445 by Barman et al. [Barman et al., 2018], leading to our approximation ratio.

Cite as

Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.63,
  author =	{Feng, Yuda and Li, Shi},
  title =	{{A Note on Approximating Weighted Nash Social Welfare with Additive Valuations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.63},
  URN =		{urn:nbn:de:0030-drops-202068},
  doi =		{10.4230/LIPIcs.ICALP.2024.63},
  annote =	{Keywords: Nash Social Welfare, Configuration LP, Approximation Algorithms}
}

Search Results

Documents authored by Feng, Yuda

New Convex Programming Technique for Nash Social Welfare and Scheduling

Abstract

Cite as

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

Abstract

Cite as

Thanks for your feedback!

Could not send message