A Probabilistic Constructive Approach To Optimization Problems
Jennifer L. A. Wong, Farinaz Koushanfar, Seapahn Meguerdichian, Miodrag Potkonjak · 2001
We propose a new optimization paradigm for solving intractable combinatorial problems. The technique, named Probabilistic Constructive (PC), combines the advantages of both constructive and probabilistic algorithms. The Constructive aspect provides relatively short runtime and makes the technique amenable for inclusion of insights through heuristic rules. The probabilistic nature facilitates a flexible trade-off between runtime and the quality of solution, and super imposition of a variety of control strategies and solution selection mechanisms. In addition to presenting the generic technique, we apply it to two generic NP-complete problems (Maximal Independent Set, Graph Coloring) and a synthesis problem (Scheduling). Extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and runtime, often outperforming the best previously published approaches. 1.