Computer Science – Discrete Mathematics
Scientific paper
2009-01-25
Computer Science
Discrete Mathematics
32 pages, 8 figures
Scientific paper
The aim of this paper is to provide a review of structural decomposition methods in discrete optimization and to give a unified framework in the form of local elimination algorithms (LEA). This paper is organized as follows. Local elimination algorithms for discrete optimization (DO) problems (DOPs) with constraints are considered; a classification of dynamic programming computational procedures is given. We introduce Elimination Game and Elimination tree. Application of bucket elimination algorithm from constraint satisfaction (CS) to solving DOPs is done. We consider different local elimination schemes and related notions. Clustering that merges several variables into single meta-variable defines a promising approach to solve DOPs. This allows to create a quotient (condensed) graph and apply a local block elimination algorithm. In order to describe a block elimination process, we introduce Block Elimination Game. We discuss the connection of aforementioned local elimination algorithmic schemes and a way of transforming the directed acyclic graph (DAG) of computational LEA procedure to the tree decomposition.
No associations
LandOfFree
Graph-based local elimination algorithms in discrete optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Graph-based local elimination algorithms in discrete optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph-based local elimination algorithms in discrete optimization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-504055