<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Embedding Complexity and Discrete Optimization I: A New Divide and Conquer Approach to Discrete Optimization
D. Cieslik1, A. Dress2, K.T. Huber3, and V. Moulton4
1Institute of Mathematics and Computer Science, University of Greifswald, 17487 Greifswald Germany
2FSPM-Strukturbildungsprozesse, University of Bielefeld, 33501 Bielefeld, Germany
3Department of Biometry and Informatics, Swedish University of Agricultural Sciences, 75007 Uppsala, Sweden
4Linnaeus Center for Bioinformatics, Uppsala University, BMC, Box 598, 75124 Uppsala Sweden
Annals of Combinatorics 6 (3) p.257-273 September, 2002
AMS Subject Classification: 90C60, 49L99, 05C99, 90B99
In this paper, we introduce a new and quite natural way of analyzing instances of discrete optimization problems in terms of what we call the embedding complexity of an associated more or (sometimes also) less canonical embedding of the (generally vast) solution space R of a given problem into a product of (generally many small) factor sets so that the score of a solution , interpreted as an element , can be computed additively by summing over the local scores of all of its components , for some appropriate score functions defined on the various factor sets . This concept arises naturally within the context of a general Divide & Conquer strategy for solving discrete optimization problems using dynamic-programming procedures. Relations with the treewidth concept and with linear-programming approaches to discrete optimization, as well as ways to exploit our approach to computing Boltzmann statistics for discrete optimization problems are indicated. In further papers, we will discuss these relations in more detail, concepts of data representation like e.g., PQ-trees, and we will apply the ideas developed here towards designing schemes for solving specific optimization problems, e.g., the Steiner problem for graphs.
Keywords: Optimization, discrete optimization, Divide & Conquer, dynamic programming, dynamic-programming schemes, algorithmic complexity, computational complexity, embedding complexity, treewidth, LP, linear programming, ILP, integer linear programming, Boltzmann statistics (for discrete optimization problems)


1. H.L. Bodlaender, A tourist guide through treewidth, Acta Cybernetica 11 (1993) 1每21.

2. H.L. Bodlaender, A tourist guide through treewidth (modified version), In: Developments in Theoretical Computer Science: Proceedings of the 7th International Meeting of Young Computer Scientists, Smolenice, 16每20 November 1992, J. Dassow and A. Kelemenova Eds., Gordon and Breach Science Publishers, 1994, pp. 1每20.

3. H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998) 1每45.

4. H.L. Bodlaender, Treewidth: algorithmic techniques and results, In: Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS*97, I. Privara and P. Ruzicka, Eds., Springer Lecture Notes in Computer Science, 1295, 1997, pp. 29-36.

5. S. Boecker and A. Dress, A note on maximal hierarchies, Adv. Math. 151 (2000) 270每282.

6. A. Borissenko, A. Dress, and G. Weiller, Minimum entropy trees 〞 a new heresy in phylogenetic reconstruction, manuscript, Bielefeld, 2002.

7. A. Borrissenko, D. Cieslik, A. Dress, K.T.Huber, and V.Moulton, Embedding complexity and discrete optimization IV: Boltzmann statistics for discrete optimization problems, preprint.

8. R. Burkard, V. Deineko, and G. Woeginger, The travelling salesman problem and the PQtree, Math. Oper. Res. 23 (1998) 613每623.

9. D. Cieslik, A. Dress, K.T. Huber, and V.Moulton, Embedding complexity and discrete optimization II: a dynamical programming approach to the Steiner-tree problem, Ann. Combin. 6 (2002) 275每283.

10. D. Cieslik, A. Dress, K.T. Huber, and V.Moulton, Embedding complexity and discrete optimization III: PQ-trees and the travelling-salesman problem, preprint.

11. A. Dress, Computing spin-glass Hamiltonians, manuscript, Bielefeld, 1986.

12. A. Dress, On the computational complexity of composite systems, In: Proceedings of the IX Sitges Conference in Theoret. Physics, Sitges, 1986, Springer Lecture Notes 268, 1987, pp. 377每388.

13. A. Dress and M. Kr邦ger, Parsimonious phylogenetic trees in metric spaces and simulated annealing, Adv. Appl. Math. 8 (1987) 8每37.

14. J.S. Farris and A.G. Kluge, Parsimony and history, Syst. Biol. 46 (1997) 215每218.

15. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H. Freeman and Company, 1979.

16. D. Gusfield, Algorithms on Strings Trees and Sequences, Cambridge University Press, 1997.

17. J.Setubal and J.Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.

18. M. Waterman, Introduction to Computational Biology, Chapman and Hall, 1995.