text-only page produced automatically by Usablenet Assistive Skip all navigation and go to page content Skip top navigation and go to directorate navigation Skip top navigation and go to page navigation
National Science Foundation
design element
Search Awards
Recent Awards
Presidential and Honorary Awards
About Awards
Grant Policy Manual
Grant General Conditions
Cooperative Agreement Conditions
Special Conditions
Federal Demonstration Partnership
Policy Office Website

Award Abstract #1319460

AF: Small: New Perspectives on Special Methods for Graph Algorithms

Division of Computing and Communication Foundations
divider line
Initial Amendment Date: June 20, 2013
divider line
Latest Amendment Date: June 20, 2013
divider line
Award Number: 1319460
divider line
Award Instrument: Standard Grant
divider line
Program Manager: Tracy J. Kimbrel
CCF Division of Computing and Communication Foundations
CSE Direct For Computer & Info Scie & Enginr
divider line
Start Date: September 1, 2013
divider line
End Date: July 31, 2015 (Estimated)
divider line
Awarded Amount to Date: $177,392.00
divider line
Investigator(s): Lorenzo Orecchia orecchia@bu.edu (Principal Investigator)
divider line
Sponsor: Massachusetts Institute of Technology
Cambridge, MA 02139-4301 (617)253-1000
divider line
divider line
Program Reference Code(s): 7923, 7926
divider line
Program Element Code(s): 7926


Classical algorithms for many important graph primitives were designed at a time when the conventional notion of efficiency was polynomial running time. However, many of today's applications involve graphs consisting of millions, or even billions, of nodes. On these massive inputs, practical algorithms must run in time that is as close to linear as possible in the size of the input.

The spectral approach to designing graph algorithms views the instance graph as a matrix and makes use of the algebraic properties of the corresponding linear operator. Recently, research in this area has led to the design of faster spectral algorithms for many essential graph problems, such as electrical flow, maximum flow and graph partitioning in undirected graphs. The goal of this project is to develop a novel algorithmic approach by combining spectral methods and the idea of regularization from optimization. Regularization is a mechanism for modifying a given optimization problem to make it more amenable to known algorithms without changing its salient characteristics. Surprisingly, many of the recent breakthroughs in the design of fast spectral algorithms can be viewed as applying different types of regularization. This research aims to exploit this interpretation to design algorithms that are faster, simpler to analyze and easier to implement. Another aim of this research is to integrate different perspectives on regularization from Machine Learning, Statistics and Convex Optimization, to create new bridges between these fields and the design of algorithms.

Due to the practical importance of the graph problems under consideration, the work will also focus on empirically evaluating the algorithms designed. These evaluations will be disseminated to the relevant audiences to maximize the impact of the award. Moreover, because this project aims to develop new fundamental techniques in the design of algorithms, a particular effort will be devoted to incorporating material from this research into the PI's teaching activity and to preparing educational material for the public.


Please report errors in award information by writing to: awardsearch@nsf.gov.



Print this page
Back to Top of page
Research.gov  |  USA.gov  |  National Science Board  |  Recovery Act  |  Budget and Performance  |  Annual Financial Report
Web Policies and Important Links  |  Privacy  |  FOIA  |  NO FEAR Act  |  Inspector General  |  Webmaster Contact  |  Site Map
National Science Foundation Logo
The National Science Foundation, 4201 Wilson Boulevard, Arlington, Virginia 22230, USA
Tel: (703) 292-5111, FIRS: (800) 877-8339 | TDD: (800) 281-8749
  Text Only Version