Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Madry, Aleksander http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-68890
URL:

Continuous Optimization: The “Right” Language for Graph Algorithms? (Invited Talk)

pdf-format:


Abstract

Traditionally, we view graphs as purely combinatorial objects and tend to design our graph algorithms to be combinatorial as well. In fact, in the context of algorithms, "combinatorial" became a synonym of "fast". Recent work, however, shows that a number of such "inherently combinatorial" graph problems can be solved much faster using methods that are very "non-combinatorial". Specifically, by approaching these problems with tools and notions borrowed from linear algebra and, more broadly, from continuous optimization. A notable examples here are the recent lines of work on the maximum flow problem, the bipartite matching problem, and the shortest path problem in graphs with negative-length arcs. This raises an intriguing question: Is continuous optimization a more suitable and principled optics for fast graph algorithms than the classic combinatorial view? In this talk, I will discuss this question as well as the developments that motivated it.

BibTeX - Entry

@InProceedings{madry:LIPIcs:2016:6889,
  author =	{Aleksander Madry},
  title =	{{Continuous Optimization: The “Right” Language for Graph Algorithmsl (Invited Talk)}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{4:1--4:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6889},
  URN =		{urn:nbn:de:0030-drops-68890},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.4},
  annote =	{Keywords: maximum flow problem, bipartite matchings, interior-point methods, gradient decent method, Laplacian linear systems}
}

Keywords: maximum flow problem, bipartite matchings, interior-point methods, gradient decent method, Laplacian linear systems
Seminar: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI