Lune

NeurIPS2022Top-tier venue

Fast Algorithms for Packing Proportional Fairness and its Dual

Francisco Criado, David Martínez-Rubio, Sebastian Pokutta

Abstract

The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of ∑ilog⁡xi\sum_i \log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x∈R≥0nx \in \mathbb{R}^{n}_{\geq 0}. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent. Finally, we show the latter problem has applications to the volume reduction of bounding simplices in an old linear programming algorithm of (YL82), and we obtain some improvements as a result.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral ConstraintsSven Jäger, Alexander Lindermayr, Nicole MegowSODA 2025 · 1 citation
  2. Online Generalized Network Design Under (Dis)Economies of ScaleViswanath Nagarajan, Lily WangSODA 2021 · 3 citations
  3. A Learning-Augmented Approach to Online Allocation ProblemsIlan Reuven Cohen, Debmalya PanigrahiNeurIPS 2025 · 1 citation
  4. Decentralized Optimization with Coupled ConstraintsDemyan Yarmoshik, Alexander Rogozin, Nikita Kiselev, Daniil Dorin et al.ICLR 2025
  5. Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic DepthArpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil et al.SODA 2024 · 7 citations
Dusk over the sea between two cliffs drawn in fine vertical lines