Branch-and-Bound Applications in Combinatorial Data Analysis

1. Auflage. Softcover version of original hardcover Auflage 2005
ISBN: 978-1-4419-2039-3
Verlag: Springer

Buch, Englisch, 222 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 365 g

Reihe: Statistics and Computing

This monograph focuses on the application of the solution strategy known as branch-and-bound to problems of combinatorial data analysis. Combinatorial data analysis problems typically require either the sel- tion of a subset of objects from a larger (master) set, the grouping of a collection of objects into mutually exclusive and exhaustive subsets, or the sequencing of objects. To obtain verifiably optimal solutions for this class of problems, we must evaluate (either explicitly or implicitly) all feasible solutions. Unfortunately, the number of feasible solutions for problems of combinatorial data analysis grows exponentially with pr- lem size. For this reason, the explicit enumeration and evaluation of all solutions is computationally infeasible for all but the smallest problems. The branch-and-bound solution method is one type of partial enume- tion solution strategy that enables some combinatorial data analysis pr- lems to be solved optimally without explicitly enumerating all feasible solutions. To understand the operation of a branch-and-bound algorithm, we d- tinguish complete solutions from partial solutions. A complete solution is one for which a feasible solution to the optimization problem has been produced (e. g., all objects are assigned to a group, or all objects are - signed a sequence position). A partial solution is an incomplete solution (e. g., some objects are not assigned to a group, or some objects are not assigned a sequence position).

Zielgruppe

Research

Autoren/Hrsg.

Stahl, Stephanie

Brusco, Michael J.

Fachgebiete

• Wirtschaftswissenschaften Betriebswirtschaft Wirtschaftsmathematik und -statistik
• Interdisziplinäres Wissenschaften Wissenschaften: Forschung und Information Datenanalyse, Datenverarbeitung
• Mathematik | Informatik Mathematik Operations Research
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
• Wirtschaftswissenschaften Volkswirtschaftslehre Volkswirtschaftslehre Allgemein Ökonometrie
• Mathematik | Informatik Mathematik Stochastik Mathematische Statistik

Inhaltsverzeichnis

Cluster Analysis—Partitioning.- An Introduction to Branch-and-Bound Methods for Partitioning.- Minimum-Diameter Partitioning.- Minimum Within-Cluster Sums of Dissimilarities Partitioning.- Minimum Within-Cluster Sums of Squares Partitioning.- Multiobjective Partitioning.- Seriation.- to the Branch-and-Bound Paradigm for Seriation.- Seriation—Maximization of a Dominance Index.- Seriation—Maximization of Gradient Indices.- Seriation—Unidimensional Scaling.- Seriation—Multiobjective Seriation.- Variable Selection.- to Branch-and-Bound Methods for Variable Selection.- Variable Selection for Cluster Analysis.- Variable Selection for Regression Analysis.