Approximation Algorithms for Problems of Various Complexities

    Project: Research project

    Project Details


    The purpose of this research is to design and analyze discrete algorithms

    approximating solutions to combinatorial optimization problems.Because

    many of these problems are NP-hard,an exact solution is often not feasible;

    in such cases approximation algorithms are a viable alternative.In addition

    to attacking approximation problems that seem to require new strategies,

    another main goal is to investigate the applicability of design principles de-

    veloped successfully for traditional discrete optimization problems to com-

    parable tasks occurring in other areas.In any ase,a rigorous performance

    analysis is always intended.

    A .rst focus is the #P-complete permanent problem,which is of much

    importance in statistical physics and combinatorics.Rough approximations

    (up to an exponential factor)can be obtained in deterministic polynomial

    time and possibly even mu h faster on a parallel machine.Such a solution

    would allow to solve the outstanding bipartite matching problem of parallel

    computing.Even though the matching problem is easy for a sequential

    machine,it is very hallenging to coordinate the many processors of a parallel

    machine to worksimultaneously and e .ciently on the same matching.It is

    also proposed to attackthe parallel matching problem with a novel version

    of more traditional network .ow methods.

    Another theme of this proposal is the approximation of NP-hard opti-

    mization problems by traditional methods like lo al search,the comparison

    method,semide .nite optimization,or some combination of these.It is even

    proposed to investigate the approximation of some problems in P,as this

    could have interesting applications in parallel computing.

    Effective start/end date5/15/024/30/06


    • National Science Foundation: $236,711.00


    Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.