Approximation Algorithms for Problems of Various Complexities

Pennsylvania State Univ University Park, University Park PA

Investigators

Abstract

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.