Combinatorial Optimization and Applications

front-matter......Page 0
Matchings in Graphs Variations of the Problem......Page 9
Combinatorics from Bacterial Genomes......Page 11
Terminology......Page 12
Cut Points of Metric Spaces......Page 13
Retracts......Page 14
Virtual Cut Points of Metric Spaces......Page 15
Virtual Cut Points and Additive Split of Metric Spaces......Page 16
An Algorithm for Computing the Virtual Cut Points of Finite Metric Spaces......Page 17
Introduction......Page 19
A Property of the Anti-block Coefficient......Page 21
Compute the Anti-block Vital Edge......Page 22
Algorithm* for Computing the Anti-block Vital Edge......Page 23
Applications of the Anti-block Vital Edge in Urban Traffic Networks......Page 24
Conclusions......Page 26
Introduction......Page 28
Related Work......Page 29
Algorithms to $k$-Connected Target Coverage......Page 31
$k$-Connected Augmentation Problem......Page 32
$k$-Connected Target Coverage Problem and Its Algorithm......Page 35
Performance Evaluation......Page 36
References......Page 38
Introduction and Our Contributions......Page 40
Preliminaries and Notations......Page 42
A Polynomially Solvable Special Case of BSM......Page 43
The Main Procedure......Page 44
Conclusion and Remarks......Page 46
Introduction......Page 48
Formal Definition of the Problem......Page 49
Sum-of-Pairs......Page 50
A Generic Framework for Aligning Alignments......Page 52
Experimentations......Page 54
Results......Page 55
Conclusion......Page 56
Introduction......Page 58
New Cost Function......Page 59
Problem Identification......Page 61
Formulations......Page 62
Extension to Distance Constraints......Page 64
Illustrative Examples......Page 65
Conclusion......Page 66
Introduction......Page 68
The Model of the OTLLA......Page 70
Results of Competitive Analysis......Page 71
Conclusion and Discussion......Page 75
Introduction......Page 77
Mathematical Model......Page 79
Polynomially Solvable Cases of the CMST Problem......Page 80
An Efficient Algorithm for the MRST Problem......Page 83
Concluding Remark......Page 85
Introduction......Page 87
The Nested Partitions Method......Page 88
Hybrid NP/SA Algorithm......Page 89
Convergence of NP/SA......Page 91
The Separability Criterion for Customer Feature Selection......Page 92
Hybrid NP/SA Algorithm for the Customer Feature Selection Problem......Page 93
References......Page 95
Introduction......Page 97
A Repairing Strategy......Page 99
Approximation......Page 102
Tightness of Analysis......Page 105
Conclusions......Page 107
Introduction......Page 109
Output-Sensitive Building of a Threshold BDD......Page 111
Parallel AND Operation on Threshold BDDs......Page 113
Optimal Variable Ordering of a Threshold BDD Via 0/1 IP Formulation......Page 114
Computational Results......Page 118
Introduction......Page 121
Information and Knowledge^4......Page 123
Game on Knowledge Structure^6......Page 124
Communication on Knowledge Structure......Page 125
The Result......Page 127
Concluding Remarks......Page 129
Introduction......Page 131
Group Actions and Fundamental Domains......Page 132
Separation for the Cyclic and Symmetric Groups......Page 134
Partitioning, Packing, Covering and Relations to Orbitopes......Page 135
Products of Groups......Page 136
Conclusions......Page 137
Introduction......Page 139
The Generalized Minimum Spanning Tree Problem......Page 140
An Exact Algorithm for the Generalized Minimum Spanning Tree Problem......Page 141
The Generalized Travelling Salesman Problem......Page 143
An Exact Algorithm for the Generalized Travelling Salesman Problem......Page 145
Conclusions......Page 146
Introduction......Page 148
A $O( qrt{m})$ Approximation Algorithm for Subadditive Valuations with Value Queries......Page 150
A $O(\log m)$ Approximation Algorithm for Subadditive Valuations with Demand Queries......Page 152
Conclusion and Open Problems......Page 154
Introduction......Page 156
Related Work......Page 157
Architecture......Page 158
Components of Grid Resource Discovery......Page 159
Class Formation and Maintenance......Page 160
Resource Query Processing and Message Dispatching Mechanism......Page 163
Experiment Result......Page 164
Conclusion......Page 165
Introduction......Page 167
Preliminaries......Page 168
Related Work......Page 169
Algorithm for Computing $(1,k)$-CDS......Page 170
Algorithm for Computing $(2,k)$-CDS......Page 171
Algorithm for Computing (2,1)-CDS......Page 173
Conclusion......Page 174
Introduction......Page 176
Problem Specification and the Main Results......Page 177
The New Lower Bound and Its Asymptotic Analysis......Page 178
Worst Case Analysis of NLB......Page 179
Computational Results......Page 181
Summary and Conclusions......Page 182
References......Page 184
Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp......Page 185
Introduction......Page 193
Model......Page 194
Exact Implementation......Page 195
Non-exact Implementation......Page 198
Simulation......Page 200
Average Payoff Model......Page 202
Round-Based Mechanisms......Page 203
Conclusions......Page 204
Introduction......Page 205
Preliminary......Page 207
Infinite Families of $k$-Tight Optimal Double-Loop Networks......Page 208
Infinite Families of Nus Integers......Page 211
References......Page 214
Introduction......Page 215
The Independence Number of Linear Hypergraphs......Page 216
A Deterministic Algorithm......Page 218
The Numbers of Edges in ${\mathcal G}$......Page 219
The Numbers of $2$-Cycles in ${\mathcal G}$......Page 220
Choosing a Subhypergraph in ${\mathcal G}$......Page 222
The 15 Puzzle......Page 227
An Example of a 15-Puzzle-Based Secure Computation......Page 228
Our Results and Related Work......Page 229
Our Class of Protocols......Page 230
Abstraction......Page 232
Our Protocols......Page 233
Protocols for 4-Variable General Functions......Page 235
Conclusions......Page 237
Introduction......Page 239
Previous Work......Page 240
Outline......Page 242
Solving the Extended Pairwise Alignment Problem......Page 243
Experiments......Page 246
Conclusion......Page 247
Introduction......Page 251
Problem Formulation......Page 253
Properties of an Optimal Solution for the Problem......Page 254
A Solution Algorithm......Page 257
Conclusions......Page 260
Introduction......Page 263
Parameterized Complexity and W-Hardness Under Linear FPT-Reductions......Page 265
NP Optimization Problems and Approximation Algorithms......Page 266
A Lower Bound on PTAS for the CSP Problem......Page 267
Conclusion......Page 271
Introduction......Page 273
Preliminaries......Page 275
Branch-and-Cut......Page 277
Generating Cutting Planes......Page 278
Experimental Results......Page 279
Conclusion and Future Work......Page 281
Introduction......Page 283
Main Idea......Page 286
General Computing Formulae......Page 289
Applications......Page 291
Conclusions......Page 293
Introduction and Terminology......Page 295
Analysis......Page 296
The Correctness and the Time Complexity......Page 301
Introduction......Page 303
Related Lemmas......Page 304
The Strategy for Reducing the Search Space in Algorithm EACI......Page 305
Algorithm EACI-dyn......Page 309
Putting All Together......Page 310
Conclusions......Page 312
Introduction......Page 314
Elementary Bounds......Page 316
Subdigraphs and Digraph Minors......Page 317
Characterizing 1-Searchable Digraphs......Page 318
Characterizing 2-Searchable Digraphs......Page 320
Strong Digraphs......Page 323
Further Directions......Page 324
On the Complexity of Some Colorful Problems Parameterized by Treewidth......Page 326
Introduction......Page 327
List Chromatic Number Parameterized by Treewidth Is FPT......Page 328
Some Coloring Problems That Are Hard for Treewidth......Page 330
List Coloring and Precoloring Extension are W[1]-Hard, Parameterized by Treewidth......Page 331
Equitable Coloring Is W[1]-Hard Parameterized by Treewidth......Page 332
Discussion and Open Problems......Page 336
Introduction......Page 338
The Idea......Page 341
The Algorithm......Page 342
Computing the Chain Table......Page 343
Maximizing the Weight of Non-backbone Elements with Specified Backbone Elements......Page 344
Concluding Remarks......Page 346
back-matter......Page 348