Computer Science Department
School of Computer Science, Carnegie Mellon University
Hybrid Algorithsm for On-Line Search and Combinatorial Optimation Problems
Yury V. Smirnov
This thesis presents a systematic approach that attempts to advance the state of the art in the transfer of knowledge across the above mentioned areas. In this work we investigate a number of problems that belong to or are close to the intersection of areas of interest of AI, OR and CS theory. We illustrate the advantages of considering knowledge available in different scientific areas and of applying algorithms across distinct disciplines through successful applications of novel hybrid algorithms that utilize beneficial features of known efficient approaches. Testbeds for such applications in this thesis work include both open theoretical problems and ones of significant practical importance.
We introduce a representation change that enables us to question the relation between the Pigeonhole Principle and Linear Programming Relaxation. We show that both methods have exactly the same bounding power. Furthermore, even stronger relation appears to be between the two methods: The Pigeonhole Principle is the Dual of Linear Programming Relaxation. Such a relation explains the "hidden magic" of the Pigeonhole Principle, namely its power in establishing upper bounds and its effectiveness in constructing optimal solutions.
We also address various groups of problems, that arise in agent-centered search. In particular, we consider goal-directed exploration, in which search by a physical or fictitious agent with limited lookahead occurs in partially or completely unknown domains. The resulting Variable Edge Cost Algorithm (VECA) becomes the first method of solving goal-directed exploration problems that incorporates strong guidance from heuristic knowledge, yet is still capable of providing linear worst-case guarantees, even for complex search domains and misleading heuristics.
This work aims at expanding the handset of AI tools that concern search efficiency and provides the foundation for further development of hybrid methods, cross-fertilization and successful applications across AI, CS theory, OR and other Computational Sciences.