Fast Algorithms for Packing Proportional Fairness and its Dual
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 , is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and . 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.
Related papers
- The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral ConstraintsSven Jäger, Alexander Lindermayr, Nicole MegowSODA 2025 · 1 citation
- Online Generalized Network Design Under (Dis)Economies of ScaleViswanath Nagarajan, Lily WangSODA 2021 · 3 citations
- A Learning-Augmented Approach to Online Allocation ProblemsIlan Reuven Cohen, Debmalya PanigrahiNeurIPS 2025 · 1 citation
- Decentralized Optimization with Coupled ConstraintsDemyan Yarmoshik, Alexander Rogozin, Nikita Kiselev, Daniil Dorin et al.ICLR 2025
- Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic DepthArpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil et al.SODA 2024 · 7 citations
