ARC Seminar - László Végh - Georgia Tech

Event Details
  • Date/Time:
    • Monday February 27, 2012
      12:00 pm
  • Location: Klaus 1116 West, Atlanta, GA
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: Strongly polynomial algorithm for a class of minimum-cost flow

Full Summary: No summary paragraph submitted.


Abstract

A well-studied nonlinear extension of the minimum-cost flow problemis to minimize the objective \sum_{ij\in E} C_{ij}(f_{ij}) over feasible flows f, where on each arc ij of the network, C_{ij} is a convex function. We give a strongly polynomial algorithm for finding  an exact optimal solution for a broad class of such problems, The class includes convex quadratic objectives; thereby we give the first strongly polynomial algorithms for separable convex quadratic
minimum-cost flows, settling a long-standing open question. Further applications include market equilibrium problems, in particular, we give the first strongly polynomial algorithm for Fisher's market with spending constraint utilities.

Additional Information

In Campus Calendar
Yes
Groups

School of Computer Science, ARC

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Feb 20, 2012 - 12:04pm
  • Last Updated: Oct 7, 2016 - 9:57pm