Abstract

A phase transition refers to such a phenomenon of a system (or combinatorial problem) in which some global properties change rapidly and dramatically when a control parameter crosses a critical value. A simple example of phase transition is water changing phases from solid (ice) to liquid (water) to gas (steam) as the temperature increases. The backbone of a problem is the fraction of variables that have fixed values among all solutions. The concepts of phase transitions and backbones have been used to characterize typical-case properties of combinatorial problems and algorithms in recent years. In this talk, I will discuss some of the important research on understanding combinatorial optimization problems using phase transitions and backbones and the work on developing new heuristic search methods that exploit such intrinsic properties of difficult problems. I will specifically focus on the results on the Traveling Salesman Problem and (maximum) Boolean satisfiability in the talk.

Dr. Weixiong Zhang is Associate Professor in computer science at Washington University in Saint Louis. He received his B.S. and M.S. in computer engineering from Tsinghua University, Beijing, China, in 1983 and 1984, and his Ph.D. in computer science from UCLA in 1994. From 1994 to 2000, he was Senior Scientist at Information Sciences Institute of USC. Dr. Zhang's research areas include artificial intelligence (heuristic search, distributed multiagent systems), combinatorial optimization and computational biology.