Dynamic Programming Multi-Objective Combinatorial Optimization (Studies in Systems, Decision and Control, 331)

Preface
Acknowledgements
Contents
1 Introduction
	1.1 Circuits Without Repetitions and Combinatorial Optimization Problems
	1.2 Beyond Conventional Circuits Without Repetitions
	1.3 Comparison with Other Investigations
	1.4 Book Contents
		1.4.1 Part I. Circuits Without Repetitions. Main Tools
		1.4.2 Part II. Combinatorial Optimization Problems. Conventional Circuits
		1.4.3 Part III. Multi-Stage and Bi-Criteria Optimization of Matchings in Trees
		1.4.4 Part IV. Combinatorial Optimization Problems. Syntactical Circuits
	1.5 Software Development
	1.6 Use of Book
	References
Part I Circuits Without Repetitions. Main Tools
2 Circuits and Cost Functions
	2.1 Circuits
	2.2 Cost Functions
	2.3 Syntactical Circuits
	2.4 Algorithms Over Circuits
		2.4.1 Schemes of Circuits
		2.4.2 Adapted Cost Functions
		2.4.3 Bounds on Number of Operations
		2.4.4 Bounds on Time Complexity
	References
3 Multi-Stage Optimization and Counting Optimal Elements
	3.1 Algorithm for Optimization of Elements
	3.2 Multi-Stage Optimization and Totally Optimal Elements
	3.3 Algorithm for Counting Elements
	References
4 Bi-Criteria Optimization of Elements
	4.1 Tools for Study of Pareto Optimal Points
	4.2 Bi-Criteria Optimization of Elements
		4.2.1 Totally Optimal Elements
	4.3 Modification of the Algorithm mathcalA4: Processing of Functional Nodes
	4.4 Relationships Between Two Cost Functions
	References
Part II Combinatorial Optimization Problems. Conventional Circuits
5 Matrix Chain Multiplication
	5.1 Definition of Circuit and Cost Functions
	5.2 Time Complexity of Algorithms
	5.3 Example
	5.4 Experiments
	References
6 Global Sequence Alignment
	6.1 Definition of Circuit and Cost Functions
	6.2 Time Complexity of Algorithms
	6.3 Example
	6.4 Experiments
	References
7 Optimal Paths in Directed Graphs
	7.1 Definition of Circuit and Cost Functions
	7.2 Time Complexity of Algorithms
	7.3 Example
	7.4 Experiments
	References
8 Binary Search Trees
	8.1 Definition of Circuit and Cost Functions
	8.2 Time Complexity of Algorithms
	8.3 Example
	8.4 Experiments
	References
9 Convex Polygon Triangulation
	9.1 Definition of Circuit and Cost Functions
	9.2 Time Complexity of Algorithms
	9.3 Example
	9.4 Experiments
	References
10 Line Breaking
	10.1 Definition of Circuit and Cost Functions
	10.2 Time Complexity of Algorithms
	10.3 Example
	10.4 Experiments
	References
11 One-Dimensional Clustering
	11.1 Definition of Circuit and Cost Functions
	11.2 Time Complexity of Algorithms
	11.3 Example
	11.4 Experiments
	References
12 Optimal Bitonic Tour
	12.1 Definition of Circuit and Cost Functions
	12.2 Time Complexity of Algorithms
	12.3 Example
	12.4 Experiments
	Reference
13 Segmented Least Squares
	13.1 Definition of Circuit and Cost Functions
	13.2 Time Complexity of Algorithms
	13.3 Example
	13.4 Experiments
	References
Part III Multi-Stage and Bi-Criteria Optimization of Matchings in Trees
14 Discussion of Matching Optimization Problem and Representation of Matchings
	14.1 Discussion of Matching Optimization Problem
	14.2 Representation of Matchings in Trees
	References
15 Counting Matchings and Multi-Stage Optimization of Matchings
	15.1 Counting Matchings
	15.2 Multi-Stage Optimization of Matchings
	Reference
16 Bi-Criteria Optimization of Matchings
	16.1 Fusion of Sets of Pareto Optimal Points
	16.2 Bi-Criteria Optimization of Matchings
	16.3 Totally Optimal Matchings
	References
17 Example and Experimental Results
	17.1 Example
	17.2 Experimental Results
	References
Part IV Combinatorial Optimization Problems. Syntactical Circuits
18 Optimization of Matchings in Trees
	18.1 Definition of Circuit and Cost Functions
	18.2 Time Complexity of Algorithms
	18.3 Example
	18.4 Experiments
	18.5 Comparison with Results from Part III
	References
19 0/1 Knapsack Problem
	19.1 Definition of Circuit and Cost Functions
	19.2 Time Complexity of Algorithms
	19.3 Example
	19.4 Experiments
	References
Appendix  Final Remarks
Index