Professor László Végh (Department of Mathematics, London School of Economics and Political Science) will be a guest of the Corvinus Center for Operation Research (CCOR) the next two weeks. As part of his visit, a minicourse and a workshop will be organized.
Minicourse: Combinatorial interior point methods and strongly polynomial computability
Venue: Corvinus University, Building C
Date:
September 13 (Wednesday), 9:50 – 11:20, Room C.417
September 13 (Wednesday), 13:40 – 15:10, Room C.714
September 14 (Thursday), 14:20 – 15:50, Room C.204
CCOR Workshop
Venue: Corvinus University, Building C, Room C.714
Date: September 15 (Friday), 2023
Time: 10:00-14:30
Keynote speaker: László Végh (London School of Economics and Political Science)
Program:
10:00-10:30 Anita Varga: A new long-step interior point framework and a related function class for LP
10:30-11:00 Tibor Illés: Predictor-corrector interior-point algorithms based on a new class of algebraically equivalent transformations
11:00-13:00 Lunch break
13:00-14:00 László Végh: Approximating Nash Social Welfare by Matching and Local Search
14:00-14:30 Discussion
Abstracts
Minicourse: Combinatorial interior point methods and strongly polynomial computability
Breakthrough results in the 1980s led to the first polynomial-time algorithms for linear programming: the ellipsoid and interior point methods. However, the running time of these algorithms depends on the bit-complexity of the input. It remains a major open problem to find a strongly polynomial algorithm, where the number of arithmetic operations only depends on the number of variables and constraints.
Such algorithms are known for various network optimization problems. For general linear programs, the best known bounds depend on certain condition numbers of the constraint matrix. Somewhat surprisingly, the strongest results in this context arise using interior point methods (IPMs). An intriguing 1996 paper by Vavasis and Ye introduced a combinatorial IPM variant, called layered least squares IPM that inspired a number of further developments.
The minicourse will give an overview of classical and recent developments on combinatorial interior point methods, highlighting also the importance of the circuit imbalance measure, a key underlying parameter. I will also present a recent IPM that achieves that is essentially optimal in the strongly polynomial sense. Further, I will mention lower bounds that show that ultimately no path following IPM can be strongly polynomial.
CCOR Workshop
László Végh: Approximating Nash Social Welfare by Matching and Local Search
The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. For any ε>0, we give a deterministic (4+ε)-approximation algorithm for the NSW under submodular valuations, improving on the previous best approximation factor of 380. Our algorithm is very simple, using a combination of matching and local search techniques.
This is joint work with Jugal Garg (UIUC), Edin Husić (IDSIA), Wenzheng Li (Stanford), and Jan Vondrák (Standford)
Tibor Illés: Predictor-corrector interior-point algorithms based on a new class of algebraically equivalent transformations
We introduce a generic predictor-corrector (PC) interior-point algorithm (IPA) for solving sufficient linear complementarity problems. To determine the search directions we use the algebraic equivalent transformation (AET) technique. We propose a whole, new class of AET functions for which a unified complexity analysis of the PC IPA is given. We show that the PC IPA using any function of the new class of AET functions has polynomial iteration complexity in the size of the problem, the handicap of the problem’s matrix, the starting point’s duality gap and in the accuracy parameter.
Anita Varga: A new long-step interior point framework and a related function class for LP
Interior point algorithms can be categorized into short-step and long-step methods based on their step size. While short-step methods tend to have better theoretical complexity, long-step algorithms perform better in practice. In 2005, Ai and Zhang introduced the first long-step algorithm with the same iteration complexity as short-step variants.
In 2002, Darvay proposed the algebraically equivalent transformation technique for generating new search directions in interior point algorithms.
Our work combines these two methods to develop new long-step interior point methods following Ai and Zhang’s approach and using Darvay’s technique. Our primary focus is identifying suitable functions (function classes) that can be applied with Darvay’s method to ensure an Ai-Zhang-type algorithm’s desired convergence and complexity properties.
During the talk, we will present our results for the linear programming problem and shortly address the case of linear complementarity problems.