Tools
Tools
Cieslik, D., Dress, A., Huber, K. T. and Moulton, V. 
ORCID: https://orcid.org/0000-0001-9371-6435
(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
Abstract
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 |
| UEA Research Groups: | Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre |
| Depositing User: | Vishal Gautam |
| Date Deposited: | 27 Jul 2011 12:46 |
| Last Modified: | 20 Jun 2023 14:43 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/23321 |
| DOI: | 10.1007/s000260200002 |
Actions (login required)
 |
View Item |