Skip Navigation Links

Project Information

AF: SMALL: EFFICIENT APPROXIMATIONS FOR DYNAMIC PROGRAMS AND OTHER TOPICS IN ALGORITHMS

Agency:
NSF

National Science Foundation

Project Number:
1218711
Contact PI / Project Leader:
SAKS, MICHAEL
Awardee Organization:
RUTGERS THE ST UNIV OF NJ NEW BRUNSWICK

Description

Abstract Text:
This project supports new and ongoing research on several topics in algorithms and computational complexity. A major focus of the project will be certain combinatorical optimization problems, such as determining the longest common subsequence of two data sequences, that can be formulated as shortest path problems in special networks. The goal is to develop algorithms that provably give close approximations to the correct answer and are significantly faster than existing algorithms. Another goal of the project is to construct sparse spanners for networks, which are subnetworks with few edges that preserve (partially or approximately) the connectivity or distance properties of the original network. A third part of the project will seek to establish inherent limitations on the efficiency of parallel programs in the MapReduce paradigm, which is an increasingly popular paradigm for parallel programming in which computation occurs in a sequence of precisely defined rounds. The aim is to establish some inherent limitations on this model by proving lower bounds on the number of computation rounds needed for certain basic computational tasks. Another part of the project will develop new algorithms and determine limits to efficiency for the file maintenance problem, in which numbers are presented in an online manner and are loaded into a linear array (possibly with gaps between items) so that the left-to-right order of the items matches the natural order. The cost is measured by the total number of times any item is moved during the loading process. The aim here is to obtain better algorithms than the existing ones using randomization, or to establish that randomization can not significantly improve on the best existing algorithms.

By advancing the theory of algorithms and complexity, this award will increase the set of tools available for efficient design of algorithms. The algorithmic techniques developed for efficient estimation of dynamic programs may be useful for practitioners developing algorithms for problems such as string matching, which is a fundamental problem that arises in varied areas such as data retrieval and analysis of biological data. Establishing inherent requirements on computational resources for solving various problems can guide the search for improved algorithms for related problems. An important part of the project is the training of graduate students to do research in the field.
Project Terms:
Algorithms; Area; Award; Biological; Computational algorithm; Computational algorithm; computing resources; cost; Data; Data Analyses; Data Storage and Retrieval; design; Goals; graduate student; improved; Left; Maintenance; Measures; Modeling; Process; programs; Property; Randomized; Research; Techniques; theories; Time; tool; Training

Details

Contact PI / Project Leader Information:
Name:  SAKS, MICHAEL
Other PI Information:
Not Applicable
Awardee Organization:
Name:  RUTGERS THE ST UNIV OF NJ NEW BRUNSWICK
City:  NEW BRUNSWICK    
Country:  UNITED STATES
Congressional District:
State Code:  NJ
District:  06
Other Information:
Fiscal Year: 2012
Award Notice Date:
DUNS Number: 001912864
Project Start Date: 01-Sep-2012
Budget Start Date:
CFDA Code: 47.070
Project End Date: 31-Aug-2015
Budget End Date:
Agency: ?

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

National Science Foundation
Project Funding Information for 2012:
Year Agency

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

FY Total Cost
2012 NSF

National Science Foundation

$400,000

Results

i

It is important to recognize, and consider in any interpretation of Federal RePORTER data, that the publication and patent information cannot be associated with any particular year of a research project. The lag between research being conducted and the availability of its results in a publication or patent award varies substantially. For that reason, it's difficult, if not impossible, to associate a publication or patent with any specific year of the project. Likewise, it is not possible to associate a publication or patent with any particular supplement to a research project or a particular subproject of a multi-project grant.

ABOUT FEDERAL REPORTER RESULTS

Publications: i

Click on the column header to sort the results

PubMed = PubMed PubMed Central = PubMed Central Google Scholar = Google Scholar

Patents: i

Click on the column header to sort the results

Similar Projects

Download Adobe Acrobat Reader:Adobe Acrobat VERSION: 3.41.0 Release Notes
Back to Top