Part I Theory
Chapter 2 Fundamentals of Optimization Algorithms
2.1. Algorithmic Problems………………………………………………………………………9
2.2. Algorithms………………………………………………..……………………………….12
2.3. Complexity of Algorithms………………………………………………………………15
2.4. Conclusion………………………………………………………………………………....21
2.5. Bibliography………………………………………………………………………………….22
Chapter 3 Some Common Combinatorial Problems and Algorithms
3.1. Algorithmic Problems in Graph Theory………………………………………...25
3.2. Constraint Satisfaction………………………………………………………………..30
3.3. Conclusion……………………………………………………………………………………33
3.4. Bibliography………………………………………………………………………………….33
Chapter 4 Recent Advances in Typical-Case Complexity
4.1. Introduction…………………………………………………………………………….....37
4.2. Heavy-Tailed Runtime Distributions…………………………………………...38
4.3. Frequent Restarts………………………………………………………………………..38
4.4. Phase Transition………………………………………………………………………...39
4.5. Empirical Hardness Models………………………………………………………….41
4.6. Algorithm Portfolios…………………………………………………………………….42
4.7. Conclusion……………………………………………………………………………………42
4.8. Bibliography………………………………………………………………………………….43
Chapter 5 Metric-Based Approximation Algorithms for Graph Cut Problems
5.1. Introduction………………………………………………………………………………..47
5.2. Preliminaries……………………………………………………………………………….49
5.3. Shortest-Paths Metrics……………………………………………………………..56
5.4. Spreading Metrics……………………………………………………………………….61
5.5. lP -Embeddings…………………………………………………………………………...65
5.6. Conclusions and Open Problems…………………………………………………..72
5.7. Bibliography………………………………………………………………………………….73
Part II Applications
Chapter 6 Optimization Issues on the Motion Planning of Kinematically Redundant Manipulators
6.1. Introduction………………………………………………………………………………..81
6.2. Inverse Manipulator Jacobian……………………………………………………...84
6.3. Redundancy Resolution…………………………………………………………………86
6.4. Singularities……………………………………………………………………………......90
6.5. Other Methods……………………………………………………………………………..93
6.6. Simulation Results…………………………………………………………………………94
6.7. Conclusion………………………………………………………………………………………96
6.8. Acknowledgements………………………………………………………………………..96
6.9. Bibliography……………………………………………………………………………….....97
Chapter 7 Suboptimal Robot Team Coordination
7.1. Introduction……………………………………………………………………………………101
7.2. The Game Theoretic Framework and Strategies……………………………102
7.3. Weight Tuning with Fuzzy PD Controller……………………………………….111
7.4. Coordination of High Level Tactical Maneuvers…………………………..118
7.5. Conclusion……………………………………………………………………………………..124
7.6. Acknowledgements…………………………………………………………………………125
7.7. Bibliography…………………………………………………………………………………...125
Chapter 8 Applying Graph Coloring to Frequency Assignment
8.1. Introduction……………………………………………………………………………………129
8.2. Graph Coloring………………………………………………………………………………...130
8.3. The Frequency Assignment Problem……………………………………………….131
8.4. Solution of FAPs with Graph Coloring…………………………………………..133
8.5. Empirical Measurements……………………………………………………………………134
8.6. Conclusion………………………………………………………………………………………..138
8.7. Acknowledgements……………………………………………………………………………140
8.8. Bibliography……………………………………………………………………………………..140
Chapter 9 Routing in the 3-Dimensional Grid
9.1. Introduction………………………………………………………………………………………145
9.2. Basic Definitions…………………………………………………………………………………146
9.3. Single Active Layer Routing………………………………………………………………..146
9.4. 3-Dimensional Channel Routing……………………………………………………………149
9.5. Conclusion…………………………………………………………………………………………..150
9.6. Acknowledgements………………………………………………………………………………151
9.7. Bibliography………………………………………………………………………………………...151
Chapter 10 Total Variation Regularization in Maximum Likelihood Estimation
10.1. Introduction……………………………………………………………………………………….155
10.2. Maximum Likelihood Estimation………………………………………………………….155
10.3. Total Variation Regularization………………………………………………………….159
10.4. Application to Positron Emission Tomography………………………………...163
10.4.1. Massively Parallel Implementation………………………………………………….164
10.4.2. PET Reconstruction Examples…………………………………………………………166
10.5. Conclusions………………………………………………………………………………………..167
10.6. Acknowledgements……………………………………………………………………………..168
10.7. Bibliography………………………………………………………………………………………….168