Combinatorial Optimization and Applications

front-matter......Page 1
Matchings in Graphs Variations of the Problem......Page 10
Combinatorics from Bacterial Genomes......Page 12
Terminology......Page 13
Cut Points of Metric Spaces......Page 14
Retracts......Page 15
Virtual Cut Points of Metric Spaces......Page 16
Virtual Cut Points and Additive Split of Metric Spaces......Page 17
An Algorithm for Computing the Virtual Cut Points of Finite Metric Spaces......Page 18
Introduction......Page 20
A Property of the Anti-block Coefficient......Page 22
Compute the Anti-block Vital Edge......Page 23
Algorithm* for Computing the Anti-block Vital Edge......Page 24
Applications of the Anti-block Vital Edge in Urban Traffic Networks......Page 25
Conclusions......Page 27
Introduction......Page 29
Related Work......Page 30
Algorithms to $k$-Connected Target Coverage......Page 32
$k$-Connected Augmentation Problem......Page 33
$k$-Connected Target Coverage Problem and Its Algorithm......Page 36
Performance Evaluation......Page 37
References......Page 39
Introduction......Page 41
Preliminaries......Page 42
Labeling Method for Trees......Page 43
Unicyclic Graphs......Page 45
$k$-Ary Cycle-Disjoint Graphs......Page 48
Approximation Algorithms......Page 50
Introduction and Our Contributions......Page 53
Preliminaries and Notations......Page 55
A Polynomially Solvable Special Case of BSM......Page 56
The Main Procedure......Page 57
Conclusion and Remarks......Page 59
Introduction......Page 61
Formal Definition of the Problem......Page 62
Sum-of-Pairs......Page 63
A Generic Framework for Aligning Alignments......Page 65
Experimentations......Page 67
Results......Page 68
Conclusion......Page 69
Introduction......Page 71
New Cost Function......Page 72
Problem Identification......Page 74
Formulations......Page 75
Extension to Distance Constraints......Page 77
Illustrative Examples......Page 78
Conclusion......Page 79
Introduction......Page 81
The Model of the OTLLA......Page 83
Results of Competitive Analysis......Page 84
Conclusion and Discussion......Page 88
Introduction......Page 90
Mathematical Model......Page 92
Polynomially Solvable Cases of the CMST Problem......Page 93
An Efficient Algorithm for the MRST Problem......Page 96
Concluding Remark......Page 98
Introduction......Page 100
A Class of Critically $m$-Neighbor-Scattered Graphs......Page 102
The Size of a Minimum Critically $m$-Neighbor-Scattered Graph......Page 104
Introduction......Page 111
The Nested Partitions Method......Page 112
Hybrid NP/SA Algorithm......Page 113
Convergence of NP/SA......Page 115
The Separability Criterion for Customer Feature Selection......Page 116
Hybrid NP/SA Algorithm for the Customer Feature Selection Problem......Page 117
References......Page 119
Introduction......Page 121
A Repairing Strategy......Page 123
Approximation......Page 126
Tightness of Analysis......Page 129
Conclusions......Page 131
Introduction......Page 133
Output-Sensitive Building of a Threshold BDD......Page 135
Parallel AND Operation on Threshold BDDs......Page 137
Optimal Variable Ordering of a Threshold BDD Via 0/1 IP Formulation......Page 138
Computational Results......Page 142
Introduction......Page 145
Information and Knowledge^4......Page 147
Game on Knowledge Structure^6......Page 148
Communication on Knowledge Structure......Page 149
 The Result......Page 151
Concluding Remarks......Page 153
Introduction......Page 155
Group Actions and Fundamental Domains......Page 156
Separation for the Cyclic and Symmetric Groups......Page 158
Partitioning, Packing, Covering and Relations to Orbitopes......Page 159
Products of Groups......Page 160
Conclusions......Page 161
Introduction......Page 163
The Generalized Minimum Spanning Tree Problem......Page 164
An Exact Algorithm for the Generalized Minimum Spanning Tree Problem......Page 165
The Generalized Travelling Salesman Problem......Page 167
An Exact Algorithm for the Generalized Travelling Salesman Problem......Page 169
Conclusions......Page 170
Introduction......Page 172
A $O( qrt{m})$ Approximation Algorithm for Subadditive Valuations with Value Queries......Page 174
A $O(\log m)$ Approximation Algorithm for Subadditive Valuations with Demand Queries......Page 176
Conclusion and Open Problems......Page 178
Introduction......Page 180
Related Work......Page 181
Architecture......Page 182
Components of Grid Resource Discovery......Page 183
Class Formation and Maintenance......Page 184
Resource Query Processing and Message Dispatching Mechanism......Page 187
Experiment Result......Page 188
Conclusion......Page 189
Introduction......Page 191
Preliminaries......Page 192
Related Work......Page 193
Algorithm for Computing $(1,k)$-CDS......Page 194
Algorithm for Computing $(2,k)$-CDS......Page 195
Algorithm for Computing (2,1)-CDS......Page 197
Conclusion......Page 198
Introduction......Page 200
Problem Specification and the Main Results......Page 201
The New Lower Bound and Its Asymptotic Analysis......Page 202
Worst Case Analysis of NLB......Page 203
Computational Results......Page 205
Summary and Conclusions......Page 206
References......Page 208
Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp......Page 209
Introduction......Page 217
Model......Page 218
Exact Implementation......Page 219
Non-exact Implementation......Page 222
Simulation......Page 224
Average Payoff Model......Page 226
Round-Based Mechanisms......Page 227
Conclusions......Page 228
Introduction......Page 229
Preliminary......Page 231
Infinite Families of $k$-Tight Optimal Double-Loop Networks......Page 232
Infinite Families of Nus Integers......Page 235
References......Page 238
Introduction......Page 239
The Independence Number of Linear Hypergraphs......Page 240
A Deterministic Algorithm......Page 242
The Numbers of Edges in ${\mathcal G}$......Page 243
The Numbers of $2$-Cycles in ${\mathcal G}$......Page 244
Choosing a Subhypergraph in ${\mathcal G}$......Page 246
Introduction......Page 251
Local Alignments with Affine Gap Penalty......Page 254
DP Formulation and Pruning......Page 255
Simulating Suffix Trie Traversal Using BWT......Page 256
Modified Dynamic Programming and Pruning......Page 257
Performance of BWT-SW......Page 259
Mathematical Analysis......Page 260
Memory for DP Tables......Page 261
The 15 Puzzle......Page 264
An Example of a 15-Puzzle-Based Secure Computation......Page 265
Our Results and Related Work......Page 266
Our Class of Protocols......Page 267
Abstraction......Page 269
Our Protocols......Page 270
Protocols for 4-Variable General Functions......Page 272
Conclusions......Page 274
Introduction......Page 276
Previous Work......Page 277
Outline......Page 279
Solving the Extended Pairwise Alignment Problem......Page 280
Experiments......Page 283
Conclusion......Page 284
Introduction......Page 288
Problem Formulation......Page 290
Properties of an Optimal Solution for the Problem......Page 291
A Solution Algorithm......Page 294
Conclusions......Page 297
Introduction......Page 300
Parameterized Complexity and W-Hardness Under Linear FPT-Reductions......Page 302
NP Optimization Problems and Approximation Algorithms......Page 303
A Lower Bound on PTAS for the CSP Problem......Page 304
Conclusion......Page 308
Introduction......Page 310
Preliminaries......Page 312
Branch-and-Cut......Page 314
Generating Cutting Planes......Page 315
Experimental Results......Page 316
Conclusion and Future Work......Page 318
Introduction......Page 320
Relaxed Linear Program Formulation......Page 321
Algorithm Design......Page 322
Analysis......Page 325
Discussion and Future Work......Page 330
Introduction......Page 332
Main Idea......Page 335
General Computing Formulae......Page 338
Applications......Page 340
Conclusions......Page 342
Introduction and Terminology......Page 344
Analysis......Page 345
The Correctness and the Time Complexity......Page 350
Introduction......Page 352
Related Lemmas......Page 353
The Strategy for Reducing the Search Space in Algorithm EACI......Page 354
Algorithm EACI-dyn......Page 358
Putting All Together......Page 359
Conclusions......Page 361
Introduction......Page 363
Elementary Bounds......Page 365
Subdigraphs and Digraph Minors......Page 366
Characterizing 1-Searchable Digraphs......Page 367
Characterizing 2-Searchable Digraphs......Page 369
Strong Digraphs......Page 372
Further Directions......Page 373
On the Complexity of Some Colorful Problems Parameterized by Treewidth......Page 375
Introduction......Page 376
List Chromatic Number Parameterized by Treewidth Is FPT......Page 377
Some Coloring Problems That Are Hard for Treewidth......Page 379
List Coloring and Precoloring Extension are W[1]-Hard, Parameterized by Treewidth......Page 380
Equitable Coloring Is W[1]-Hard Parameterized by Treewidth......Page 381
Discussion and Open Problems......Page 385
Introduction......Page 387
The Idea......Page 390
The Algorithm......Page 391
Computing the Chain Table......Page 392
Maximizing the Weight of Non-backbone Elements with Specified Backbone Elements......Page 393
Concluding Remarks......Page 395
back-matter......Page 397