UID:
edocfu_9959234708702883
Format:
1 online resource (363 p.)
Edition:
1st ed.
ISBN:
981-277-015-1
Series Statement:
Series on applied mathematics ; v. 19
Content:
The need of optimal partition arises from many real-world problems involving the distribution of limited resources to many users. The "clustering" problem, which has recently received a lot of attention, is a special case of optimal partitioning. This book is the first attempt to collect all theoretical developments of optimal partitions, many of them derived by the authors, in an accessible place for easy reference. Much more than simply collecting the results, the book provides a general framework to unify these results and present them in an organized fashion. Many well-known practical prob
Note:
Description based upon print version of record.
,
Preface; Contents; 1. Formulation and Examples; 1.1 Formulation and Classification of Partitions; 1.2 Formulation and Classification of Partition Problems over Parameter Spaces; 1.3 Counting Partitions; 1.4 Examples; 1.4.1 Assembly of systems; 1.4.2 Group testing; 1.4.3 Circuit card library; 1.4.4 Clustering; 1.4.5 Abstraction of .nite state machines; 1.4.6 Multischeduling; 1.4.7 Cache assignment; 1.4.8 The blood analyzer problem; 1.4.9 Joint replenishment of inventory; 1.4.10 Statistical hypothesis testing; 1.4.11 Nearest neighbor assignment; 1.4.12 Graph partitions
,
1.4.13 Traveling salesman problem1.4.14 Vehicle routing; 1.4.15 Division of property; 1.4.16 The consolidation of farm land; 2. Sum-Partition Problems over Single-Parameter Spaces: Explicit Solutions; 2.1 Bounded-Shape Problems with Linear Objective; 2.2 Constrained-Shape Problems with Schur Convex Objective; 2.3 Constrained-Shape Problems with Schur Concave Objective: Uniform (over f) Solution; 3. Extreme Points and Optimality; 3.1 Preliminaries; 3.2 Partition Polytopes; 3.3 Optimality of Extreme Points; 3.4 Asymmetric Schur Convexity
,
3.5 Enumerating Vertices of Polytopes Using Restricted Edge-Directions3.6 Edge-Directions of Polyhedra in Standard Form; 3.7 Edge-Directions of Network Polyhedra; 4. Permutation Polytopes; 4.1 Permutation Polytopes with Respect to Supermodular Functions - Statement of Results; 4.2 Permutation Polytopes with Respect to Supermodular Functions - Proofs; 4.3 Permutation Polytopes Corresponding to Strictly Supermodular Functions; 4.4 Permutation Polytopes Corresponding to Strongly Supermodular Functions; 5. Sum-Partition Problems over Single-Parameter Spaces: Polyhedral Approach
,
5.1 Single-Shape Partition Polytopes5.2 Constrained-Shape Partition Polytopes; 5.3 Supermodularity for Bounded-Shape Sets of Partitions; 5.4 Partition Problems with Asymmetric Schur Convex Objective: Optimization over Partition Polytopes; 6. Partitions over Single-Parameter Spaces: Combinatorial Structure; 6.1 Properties of Partitions; 6.2 Enumerating Classes of Partitions; 6.3 Local Invariance and Local Sortability; 6.4 Localizing Partition Properties: Heredity, Consistency and Sortability; 6.5 Consistency and Sortability of Particular Partition-Properties; 6.6 Extensions
,
7. Partition Problems over Single-Parameter Spaces: Combinatorial Approach7.1 Applying Sortability to Optimization; 7.2 Partition Problems with Convex and Schur Convex Objective Functions; 7.3 Partition Problems with Objective Functions Depending on Part-Sizes; 7.4 Clustering Problems; 7.5 Other Problems; Bibliography; Index
,
English
Additional Edition:
ISBN 981-270-812-X
Language:
English
