Probabilistic Analysis of Combinatorial Optimization Problems on Hypergraph Matchings.

摘要

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.