Design and Analysis of Efficent Algorithms | Computer Science and Computational Research

: Basic and Applied Simulation Science (CCS-5)

CCS Home >>> CCS-1 | CCS-2 | CCS-3 | CCS-4 | CCS-5

CCS-5 Home > Computer Science and Computational Research

Design and Analysis of Efficient Algorithms

The basic research goal is to design and analysis of efficient sequential/parallel/distributed algorithms for important combinatorial problems in location theory, communication networks, logic, high performance computing and scheduling. Motivated by the practical application, whenever possible, our research tries to blend theoretical analysis along with empirical analysis of our algorithms. We are interested in designing exact, as well as approximate algorithms.

Current research areas include:

Syntactic and Algebraic Characterizations of Efficient Approximability

The goal of this project is to provide non-trivial algebraic (and syntactic) characterizations of classes of NP- and PSPACE-hard optimization problems that are efficiently approximable. As a step in this direction, we have given algebraic characterizations of a large class of problems having polynomial time approximation schemes. In contrast, under standard complexity theoretic assumptions, we also provide lower bounds for problems specified using using certain algebraic framework.
Network Design and Location Theory

In this line of research we have been successfully investigating the complexity and approximability of several multi-criteria network design and location theoretic problems. Such problems arise in the design of communication and transportation network. Some problems investigated are especially important in the design and analysis of high speed communication networks, processor assignment and statistical clustering. Two basic lines of research currently explored are (i) multi-criteria problems and (ii) network upgrade problems.

Experimental Algorithmics

We are currently investigating the performance of several well known graph problems in an experimental context. The difference between theoretical and empirically observed performance of algorithms have yielded several new insights in the past. Our goal is further work along these lines with the aim of eventually designing algorithms that theoretically good and practically appealing. Problems being currently investigated include graph coloring problems, flow problems and geometric optimization problems.

Representative Publications:

"Upgrading Bottleneck Constrained Forests,'' S.O. Krumke, M.V. Marathe, H. Noltemeier, S.S. Ravi, and H.C. Wirth, invited paper to appear in Discrete Applied Mathematics, 1999. Preliminary version appeared in Proc. 24th Workshop in Graph Theoretic Concepts in Computer Science (WG), Aachen, Germany, pp. 215-226 (June 1998).

"Improving Minimum Cost Spanning Trees by Upgrading Nodes,'' S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi, R. Sundaram, and H.C. Wirth, in J. Algorithms, 33(1), pp. 92-111 (1999).

"Improving Spanning Trees by Upgrading Nodes,'' S.O. Krumke, M.V. Marathe, H. Noltemeier, R. Ravi, S.S. Ravi, R. Sundaram, and H.C. Wirth, invited paper to appear in Theoretical Computer Science, 221(1-2), pp 139-155 (1999). Preliminary version appeared in Proc. 24th International Colloquium on Automata, Languages and Programming (ICALP), Bologna, Italy, LNCS Vol. 1256, pp. 281--291, Springer Verlag (July, 1997).