Embedding Complexity and Discrete Optimization I: A New Divide and Conquer Approach to Discrete Optimization

Cieslik, D., Dress, A., Huber, K. T. and Moulton, V. (2002) Embedding Complexity and Discrete Optimization I: A New Divide and Conquer Approach to Discrete Optimization. Annals of Combinatorics, 6 (3-4). pp. 257-273. ISSN 0218-0006

Full text not available from this repository. (Request a copy)


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 $ \Pi_{e \in E} P_e $ of (generally many small) factor sets $ P_e (e \in E) $ so that the score $ s (\pi) $ of a solution $ \pi $, interpreted as an element $ \pi = (\pi_e)_{e\in E} \in \Pi_{e\in E} p_e $, can be computed additively by summing over the local scores $ s_e (\pi_e) $ of all of its components $ \pi_e $, for some appropriate score functions $ S_e (e \in E) $ defined on the various factor sets $ P_e $. 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, we will relate embedding complexity also to other 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.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 27 Jul 2011 12:46
Last Modified: 30 Sep 2021 03:46
URI: https://ueaeprints.uea.ac.uk/id/eprint/23321

Actions (login required)

View Item View Item