Graph-based local elimination algorithms in discrete optimization

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-504055

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.