Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
A well-studied nonlinear extension of the minimum-cost flow problem is that given a convex function on every arc, the objective is to minimize the sum of these function values over feasible flows. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support.
The class includes convex quadratic objectives and also certain market equilibria problems, such as Fisher’s market with linear or with spending constraint utilities. Thereby we give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher’s market with spending constraint utilities.
Speaker Details
Laszlo Vegh completed his PhD in mathematics at the Eotvos University in Budapest in 2010, working in the Egervary Research Group on Combinatorial Optimization. He did a postdoc at the Georgia Institute of Technology in 2011-12. Currently he is a lecturer (assistant professor) at the London School of Economics. He is interested in fundamental questions in combinatorial optimization related to connectivity, flows, matchings and matroids, and also applications to areas such as mathematical economics, algorithmic game theory and network design
- Series:
- Microsoft Research Talks
- Date:
- Speakers:
- Laszlo Lovasz
- Affiliation:
- London School of Economics
-
-
Jeff Running
-
Series: Microsoft Research Talks
-
-
-
-
Galea: The Bridge Between Mixed Reality and Neurotechnology
Speakers:- Eva Esteban,
- Conor Russomanno
-
Current and Future Application of BCIs
Speakers:- Christoph Guger
-
Challenges in Evolving a Successful Database Product (SQL Server) to a Cloud Service (SQL Azure)
Speakers:- Hanuma Kodavalla,
- Phil Bernstein
-
Improving text prediction accuracy using neurophysiology
Speakers:- Sophia Mehdizadeh
-
-
DIABLo: a Deep Individual-Agnostic Binaural Localizer
Speakers:- Shoken Kaneko
-
-
Recent Efforts Towards Efficient And Scalable Neural Waveform Coding
Speakers:- Kai Zhen
-
-
Audio-based Toxic Language Detection
Speakers:- Midia Yousefi
-
-
From SqueezeNet to SqueezeBERT: Developing Efficient Deep Neural Networks
Speakers:- Sujeeth Bharadwaj
-
Hope Speech and Help Speech: Surfacing Positivity Amidst Hate
Speakers:- Monojit Choudhury
-
-
-
-
-
'F' to 'A' on the N.Y. Regents Science Exams: An Overview of the Aristo Project
Speakers:- Peter Clark
-
Checkpointing the Un-checkpointable: the Split-Process Approach for MPI and Formal Verification
Speakers:- Gene Cooperman
-
Learning Structured Models for Safe Robot Control
Speakers:- Ashish Kapoor
-
-