Investigations into the nature of hard problems

点击翻译按钮获取中文摘要

Many optimization problems require a search over vast sets of possible solutions for the best solution. Examples range from the scheduling of crews to planning to solving combinatorial puzzles. These problems are frequently very difficult to solve because they involve what is called ``the combinatorial explosion''. Basically, this means that increasing the size of the problem a little bit, say from 100 units to 110, may cause a hugely disproportionate increase in the number of cases that have to be considered. My research attempts to understand the issues inherent in developing effective algorithms for problems of this type.  Even when the possibility of exponential blow-up lies within a problem, many large instances of the problem may be easy to solve in practice. Trying to understand what distinguishes the hard from the easy instances is one of the approaches to developing better algorithms.