|
Much of the theoretical research of the 1970's consisted in
a classification of decision problems as either solvable exactly
in polynomial time, or NP-complete. Similarly, the main effort of
current algorithmic research is in classifying optimization problems
according to how well they can be approximated in polynomial time. This classification is our first (theoretical) long-term objective. To this end the project will focus on identifying cornerstone problems, finding reductions among them and understanding the combinatorial structures that lead to efficient approximation algorithms. For on-line problems, the current priority concerns a critical revision and empirical validation of its basic premises, modeling assumptions and algorithmic techniques. |