| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 20, 2000 |
| Latest Amendment Date: | March 9, 2001 |
| Award Number: | 9988348 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Robert B Grafton
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | July 1, 2000 |
| End Date: | June 30, 2005 (Estimated) |
| Total Intended Award Amount: | $197,360.00 |
| Total Awarded Amount to Date: | $276,729.00 |
| Funds Obligated to Date: |
FY 2001 = $79,369.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1350 BEARDSHEAR HALL AMES IA US 50011-2103 (515)294-5225 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
1350 BEARDSHEAR HALL AMES IA US 50011-2103 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | NUMERIC, SYMBOLIC & GEO COMPUT |
| Primary Program Source: |
01000102DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
TITLE: Topics in Parametric Optimization
ID: 9988348
PI: David Fernandez-Baca
ABSTRACT
Parametric problems are those whose input depends continuously on one or
more values. This award supports work in two fundamental areas in
parametric optimization. The first is fixed-dimensional optimization,
with special emphasis on problems whose objective function can be
efficiently evaluated at any point by a well-behaved algorithm. Problems
of this sort arise, for example, in Lagrangian relaxation. The main
question is to determine the conditions under which evaluation is as easy
as global optimization, within the context of Megiddo's method of
parametric search. The second area to be investigated is the construction
of parameter space decompositions yielding optimal solutions for all
parameter values. One issue is obtaining bounds on the number of regions
of the decomposition. This will be studied in part within a framework
that captures the essence of problems as diverse as stable marriage and
evolutionary tree construction. Another question is whether one can
accelerate the construction of the decomposition by exploiting structural
similarities between adjacent regions.
Please report errors in award information by writing to: awardsearch@nsf.gov.
