DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Probabilistic Analysis of Combinatorial Optimization Problems on Hypergraph Matchings
Final rept. Mar 2009-Nov 2011
IOWA UNIV IOWA CITY
Pagination or Media Count:
This research project was concerned with probabilistic analysis of a class of discrete optimization problems whose underlying combinatorial structure is based on hypergraph matchings. The primary goal of was to provide theoretical insights into characteristic behavior and properties of this class of problems, which would furnish guidelines for development and tuning of solution algorithms, both exact and heuristic, as well as determine amenability of this class of problems to particular types of solution methods. We have established convergence limits for the optimal values of randomized hypergraph matching problems, along with the corresponding convergence rates, and proposed algorithms for finding solutions with guaranteed quality. For hypergraph matching problems with linear objectives, this task reduces to finding k-cliques in specially constructed k-partite graphs, for which a new branch-and-bound algorithm was developed that employs bit parallelism to achieve significant computational improvements over existing methods. In a related development, the behavior of quasi-cliques in random graphs was investigated, and it was ascertained that the size of the maximum quasi-clique undergoes a first-order phase transition, one of the first results of this kind.
APPROVED FOR PUBLIC RELEASE