Handbook of approximation algorithms and metaheuristics

Handbook of Approximation Algorithms and Metaheuristics......Page 4
Dedication......Page 6
Preface......Page 7
About the Cover......Page 9
About the Editor......Page 10
Contributors......Page 11
Contents......Page 15
Part I: Basic Methodologies......Page 20
1.1 Introduction......Page 21
1.2.1 Approximation Algorithms......Page 22
1.2.2 Local Search, Artificial Neural Networks, and Metaheuristics......Page 28
1.3.1 Time and Space Complexity......Page 30
1.3.2 NP-Completeness......Page 31
1.3.3 Performance Evaluation of Algorithms......Page 32
References......Page 37
2.2 Restriction......Page 40
2.2.1 Scheduling......Page 41
2.2.2 Partially Ordered Tasks......Page 42
2.3.1 Independent Tasks......Page 44
2.4 Relaxation: Linear Programming Approach......Page 47
2.5 Inapproximability......Page 51
2.6 Traditional Applications......Page 52
2.7 Computational Geometry and Graph Applications......Page 53
2.8 Large-Scale and Emerging Applications......Page 54
References......Page 56
3.1 Introduction......Page 58
3.2 Steiner Trees......Page 59
3.3 Traveling Salesperson Tours......Page 60
3.4 Covering Points by Squares......Page 62
3.5 Rectangular Partitions......Page 63
3.6 Routing Multiterminal Nets......Page 64
3.7.1 Embedding Hyperedges in a Cycle......Page 66
3.8 Concluding Remarks......Page 67
References......Page 68
4.2 Set Cover......Page 70
4.2.2 Shortest Superstring Problem......Page 71
4.4 K-Centers......Page 72
4.5 Connected Dominating Sets......Page 73
4.7 Minimum-Degree Spanning Trees......Page 74
4.9 Primal-Dual Methods......Page 75
4.10.1 Max Cut......Page 77
4.10.3 Unweighted Set Cover......Page 78
4.10.4 Lagrangian Relaxation for Fractional Set Cover......Page 80
4.11 Conclusions......Page 81
References......Page 82
5.1 Introduction......Page 84
5.2 A Review of the Greedy Algorithm......Page 85
5.3 Directed Steiner Problems......Page 87
Layering......Page 88
Limiting the Number of Layers......Page 89
Description......Page 90
Density......Page 91
Bounding the Density of Augmenting Trees......Page 92
Approximation of k-DST......Page 93
5.5 Improving the Running Time......Page 94
Reducing the Maximum Degree......Page 95
The Modified Algorithm......Page 96
Acknowledgments......Page 97
Height Reduction......Page 98
References......Page 99
6.1 Introduction......Page 100
6.2 Rounding......Page 101
6.3 Randomized Rounding......Page 105
6.4 Metric Spaces......Page 106
References......Page 110
7.1 Introduction......Page 111
7.2.1 Independent Rounding......Page 112
7.2.2.1 Simultaneous Rounding......Page 113
7.2.2.3 Extensions......Page 114
7.3.2 Filter and Round......Page 115
7.3.3 Iterated Rounding......Page 116
7.3.4 Pipage Rounding......Page 117
7.3.5 Decompose and Round......Page 118
References......Page 120
8.1 Introduction......Page 122
8.2 Complex Quadratic Optimization......Page 125
8.3 Discrete Problems Where Q Is Positive Semidefinite......Page 127
8.5 Continuous Problems Where Q Is Not Positive-Semidefinite......Page 130
8.6 Discrete Problems Where Q Is Not Positive-Semidefinite......Page 134
References......Page 136
9.1 Introduction......Page 138
9.2.1 Extending Partial Small-Size Solutions......Page 139
9.2.1.1 Extending an Optimal Solution for a Single Subset......Page 140
9.2.1.2 Extend All Possible Solutions for Small Subsets......Page 141
9.2.2.1 Grouping Subsets of Elements......Page 142
9.2.2.2 Reducing the Number of Distinct Values in the Input......Page 143
Randomized Grouping......Page 146
9.3.1 Solving LP for a Subset of Elements......Page 147
9.3.2 LP Rounding Combined with Enumeration......Page 149
A Scheme for CIP…......Page 152
9.4 Approximation Schemes for Geometric Problems......Page 153
9.4.1 Randomized Dissection......Page 154
9.4.2 Shifted Plane Partitions......Page 155
References......Page 156
10.2 Rounding......Page 159
10.3 Interval Partitioning......Page 163
10.4 Separation......Page 164
10.6.1 Notation......Page 165
10.6.2 Extended Bellman–Ford Algorithm......Page 167
10.6.3 Rounding......Page 168
10.6.4 Interval Partitioning and Separation......Page 169
10.6.7 Hybrid Interval Partitioning Heuristics (HIPHs)......Page 170
10.6.9 Summary......Page 172
References......Page 173
11.1 Introduction......Page 174
11.2 Summary of Algorithms and Techniques......Page 175
11.3 Asymptotic Polynomial-Time Approximation Scheme......Page 176
11.3.1 Restricted Bin Packing......Page 177
11.3.3 Linear Grouping......Page 179
11.4 Asymptotic Fully Polynomial-Time Approximation Scheme......Page 181
11.4.1 Fractional Bin Packing and Rounding......Page 182
11.4.2 AFPTAS for Bin Packing......Page 184
11.5 Related Results......Page 185
References......Page 187
12.1 Introduction......Page 189
Problem SET COVER......Page 190
12.2.4 A Randomized Rounding Approximation to Set Cover......Page 191
12.3 Approximate Counting Using the Markov Chain Monte Carlo Method......Page 193
12.3.1 Radiocolorings of Graphs......Page 194
12.3.2 Outline of Our Approach......Page 195
12.3.4 Rapid Mixing......Page 196
12.3.5 An FPRAS for Radiocolorings with lambda Colors......Page 198
References......Page 199
13.1 Introduction......Page 201
13.2 Small Dominating Sets......Page 202
13.2.1 Greedy......Page 203
13.2.2 Greedy Hordes......Page 204
13.2.3 Small Connected Dominating Sets......Page 206
13.3 Coloring: The Extraordinary Career of a Trivial Algorithm......Page 207
13.3.1 Coloring with Martingales......Page 209
13.4 Matchings......Page 211
13.4.1 Distributed Maximal Independent Set......Page 212
13.5 LP-Based Distributed Algorithms......Page 214
13.6 What Can and Cannot Be Computed Locally?......Page 217
13.6.1 A Case Study: Minimum Spanning Tree......Page 218
References......Page 220
14.1 Introduction......Page 223
14.2.1 Analysis on Single Instances......Page 224
14.2.3 Comparative Analysis on Single Instances......Page 226
14.2.4 Comparative Analysis on Instance Ensembles......Page 227
14.3 Optimisation Algorithms......Page 229
14.3.1 Analysis on Single Instances......Page 230
14.3.3 Analysis on Instance Ensembles......Page 232
14.4.2 Impact of Parameter Settings......Page 233
14.4.3 Stagnation Detection......Page 234
14.4.4 Functional Characterisation of Empirical RTDs......Page 235
14.5 Extensions......Page 236
References......Page 237
15.1 Introduction......Page 240
15.2 Basic Definitions......Page 241
15.3 The Linear Reducibility......Page 244
15.4 Strict Reducibility and Complete Problems in NPO......Page 245
15.5 AP-Reducibility......Page 247
15.6.2 APX-Completeness......Page 249
15.6.3 Negative Results Based on APX-Completeness......Page 251
15.7 FT-Reducibility......Page 252
15.8 Gadgets, Reductions, and Inapproximability Results......Page 253
References......Page 254
16.1 Introduction......Page 256
16.2 Toward a New Measure of Approximation Paradigm......Page 257
16.3.1 Min Hereditary Cover......Page 259
16.3.1.1 Min Coloring......Page 260
16.3.1.2 Bin Packing......Page 261
16.3.2 Traveling Salesman Problems......Page 262
16.4 Asymptotic Differential Approximation Ratio......Page 263
16.5.2 The Class 0-DAPX......Page 265
16.5.3 DAPX- and Poly-DAPX-Completeness......Page 266
16.5.3.2 Poly-DAPX-Completeness......Page 267
16.6 Discussion and Final Remarks......Page 268
References......Page 269
17.1 Introduction......Page 272
Inapproximability......Page 273
17.2.1 The Emergence of the PCP Theory......Page 274
17.4 Gap Problems, Karp Reductions, and the PCP Theorem......Page 275
Karp reduction from languages to gap problems......Page 276
Probabilistic Oracle Machines (POM)......Page 277
FGLSS (Feige–Goldwasser–Lovasz–´Safra–Szegedy) transformation......Page 278
17.7 Codes and PCPs......Page 279
The Long Code......Page 280
17.8 Holographic Proofs and the Proof Recursion Idea......Page 281
Reducing the Query Size......Page 282
Composed Verifier......Page 283
Reducing the Alphabet Size......Page 284
Powering......Page 285
References......Page 286
Part II: Local Search, Neural Networks, and Metaheuristics......Page 288
18.1 Introduction......Page 289
Algorithm IterativeImprovement (S, N, c)......Page 290
18.1.2 The Complexity of Computing Local Optimum Solutions......Page 291
18.1.3 Local Search in Approximation Algorithms......Page 292
18.2 An Approximation Algorithm for Multiprocessor Scheduling......Page 293
18.3 Finding Spanning Trees with Many Leaves......Page 295
18.4.1 Local Search Algorithm for the k-Median Problem......Page 298
References......Page 302
19.1 Introduction......Page 304
19.2 Iterative Improvement......Page 306
Simulated Annealing......Page 308
Dynamic Local Search......Page 309
Iterated Local Search......Page 310
19.5 Population-Based SLS Methods......Page 311
Evolutionary Algorithms......Page 312
19.6 Discussion and Research Directions......Page 313
References......Page 314
20.1 Introduction......Page 317
20.2.1 Partitioning Problems and Multiexchange Neighborhoods......Page 318
20.2.1.1 Local Augmentation Algorithm for N(S)......Page 320
Path Exchange as a Cyclic Exchange......Page 321
20.3 Extended Neighborhoods and Domination Analysis......Page 323
20.4 Approximate Local Search......Page 326
Algorithm Epsilon-local search......Page 327
Acknowledgments......Page 328
References......Page 329
21.1 Introduction: The Role of the User in Heuristics......Page 332
21.1.2 Asymptotic Results Are Irrelevant for Optimization......Page 333
21.2.1 Prohibition-Based Diversification: Tabu Search......Page 334
21.2.2.2 The Escape Mechanism......Page 335
21.2.3.1 Fast Algorithms for Using the Search History......Page 336
Hashing Combined with Persistent Red-Black Trees......Page 337
21.4 Applications of Reactive Search and the Maximum Clique Example......Page 340
21.4.1 Reactive Local Search for Max Clique......Page 341
21.4.1.1 Choice of the Best Neighbor......Page 342
21.4.1.2 Reaction and Periodic Restart......Page 343
21.5 Related Reactive Approaches......Page 344
References......Page 345
22.1 Introduction......Page 349
22.2 Feedforward Neural Networks......Page 350
22.2.1 Approximation Properties......Page 352
22.2.3 Learning Theoretic Results......Page 353
22.2.3.1 VC-Dimension Approach......Page 354
22.3.1.1 Network Definition and Performance Measure......Page 355
22.3.1.2 Unrolling a Network......Page 356
22.3.1.3 Derivation of BPTT Formulation......Page 357
22.3.1.4 Real-Time Backpropagation through Time......Page 358
22.3.2 Computational Capabilities of Discrete and Continuous Recurrent Networks......Page 359
References......Page 360
23.1 Introduction......Page 363
23.2 Memory Structures......Page 365
23.3 Search Strategies......Page 367
23.4 Advanced Designs: Strategic Oscillation and Path Relinking......Page 368
23.5 The Linear-Ordering Problem......Page 370
23.6 The Tabu Cycle and Conditional Probability Methods......Page 372
References......Page 373
24.1 Introduction......Page 375
24.2 Evolutionary Algorithms......Page 376
Reproduction Operators......Page 378
Exploitation versus Exploration......Page 380
24.2.1 Families of Evolutionary Algorithms......Page 381
Constrained Problems......Page 382
Multiobjective Problems......Page 383
24.4 EAs in the Context of Metaheuristics......Page 384
Acknowledgments......Page 386
References......Page 387
25.1 Introduction......Page 390
25.2 Basic Simulated Annealing......Page 391
25.3.2 Dynamic Cooling Schedules......Page 393
25.4 Asymptotic Convergence......Page 394
25.5 Equilibrium Statistics......Page 396
References......Page 399
26.2 From Biology to Algorithms......Page 401
26.2.1 Ants......Page 402
26.2.2 Algorithms......Page 403
26.3 The Ant Colony Optimization Metaheuristic......Page 404
UpdatePheromones......Page 405
26.3.1 Example: The Traveling Salesman Problem......Page 406
26.4.1 Ant System......Page 407
26.4.2 MAX-MIN Ant System......Page 408
26.4.3 Ant Colony System......Page 409
26.5.2 Parallel ACO Implementations......Page 410
References......Page 411
27.1 Introduction......Page 415
27.2 Dissecting a Basic Memetic Algorithm......Page 416
27.4 Conclusions and Future Directions......Page 420
References......Page 421
Part III: Multiobjective Optimization, Sensitivity Analysis, and Stability......Page 427
28.1 Introduction......Page 428
Min Max Optimality......Page 429
28.2.3.1 NP-Completeness......Page 430
28.2.3.2 Intractability......Page 431
28.3.1.1 A Biobjective Scheduling Problem......Page 432
28.3.2.1 The Bicriteria Shortest Path Problem on Acyclic Graphs......Page 433
28.3.3.1 The Bicriteria MAX-CUT Problem......Page 435
28.3.4 Pareto Set Approach......Page 437
28.3.4.2 An Approximate Pareto Set with a Budget Approach......Page 438
28.3.4.3 The Bicriteria TSP (1, 2)......Page 439
References......Page 441
29.1 Introduction......Page 443
29.2 Basics......Page 444
29.3 Component-Wise Acceptance Criterion......Page 445
Extensions of Tabu Search......Page 446
29.3.2 Indirect Use of the Component-Wise Ordering......Page 447
29.4 Scalarized Acceptance Criterion......Page 448
Proprietary Simulated Annealing......Page 449
29.5.1 Sequential Combination......Page 450
29.5.2 Iterative Combination......Page 451
29.6 Conclusions......Page 452
Acknowledgments......Page 453
References......Page 454
30.1 Introduction......Page 458
30.2 Preliminaries......Page 459
30.3 Issues in Sensitivity Analysis......Page 460
30.4.1 Parametric Search......Page 462
30.4.3 Combinatorial Complexity Bounds for Small-Dimensional Problems......Page 464
30.5.1 Linear Programming......Page 465
30.5.3 Shortest Paths and Related Problems......Page 466
30.6 Sensitivity Analysis of NP-Hard Problems......Page 467
30.6.1.1 Graphs of Bounded Tree Width......Page 468
30.6.2.1 kappa Best Solutions and Sensitivity Analysis......Page 469
References......Page 470
31.1 Introduction......Page 475
31.2 Definition of the Stability of Approximation Algorithms......Page 476
31.3 Stable Approximation Algorithms for the TSP......Page 478
31.4 Lower Bounds and the Situation Inside Delta-TSP......Page 484
31.5 Discussion and Related Work......Page 486
References......Page 487
Part IV: Traditional Applications......Page 489
32.1 Introduction......Page 490
32.2 Online Algorithms......Page 491
32.2.1 Bounded-Space Online Algorithms......Page 492
32.2.2 Better Online Algorithms......Page 494
32.2.3 Lower Bounds for Online Algorithms......Page 495
32.4 Offline Algorithms......Page 496
32.5.1 Special Case Optimality......Page 499
32.5.2 Linear-Time Algorithms......Page 500
32.5.4 Absolute Worst-Case Ratios......Page 502
32.5.6 Parallel Algorithms......Page 504
References......Page 505
33.1 Introduction......Page 508
33.2 Maximizing the Number of Items Packed......Page 509
33.3 Bounds on the Number of Items per Bin......Page 511
33.4 Dynamic Bin Packing......Page 513
33.5.2 Fragmentable Bin Packing......Page 515
33.5.3 Packing Nodes of Graphs......Page 516
33.6 Changing the Bin Size......Page 517
References......Page 519
34.2 Variable-Sized Bin Packing......Page 521
34.3 Bin Covering......Page 526
References......Page 530
35.1 Introduction......Page 532
35.2 Next Fit Decreasing Height......Page 533
35.3.1 Online Results......Page 534
35.3.2 Offline Results......Page 535
35.4 Two-Dimensional Bin Packing......Page 536
35.4.2 Offline Results......Page 537
35.5.1 Online and Offline Results......Page 538
35.6 Three- and More Dimensional Bin Packing......Page 539
35.7 Vector Packing......Page 540
35.8.2 Items Appear from the Top......Page 541
35.8.4 Packing Rectangles in a Single Rectangle......Page 542
References......Page 543
36.1 Introduction......Page 547
36.2 Rectangle Packing Problem......Page 548
36.3 Coding Schemes for Rectangle Packing......Page 550
36.4 Heuristics for Rectangle Packing......Page 552
36.5 Metaheuristics for Rectangle Packing......Page 555
36.6 Irregular Packing Problem......Page 556
References......Page 559
37.1 Introduction......Page 562
Job Interval Stabbing Problem (JIS)......Page 563
Previous Research......Page 564
37.2.1 The Local Covering Algorithm for the Weighted Set Packing Problem......Page 565
37.2.2 Algorithm ALG1......Page 569
37.3 The Case of Unit Demands: Algorithm ALG2......Page 572
References......Page 576
38.1 Introduction......Page 577
Requirement......Page 578
38.2.2 Additional Definitions......Page 579
38.3.2.1 Results for Metric Instances......Page 580
38.3.2.2 Results for Geometric Versions......Page 582
38.3.3.1 Results for Metric Instances......Page 583
38.3.3.2 Results for Nonmetric Instances......Page 585
38.3.4 Results for Other Dispersion Problems......Page 586
Requirement......Page 587
38.4.2.2 Results for Maximizing Internode Distance......Page 588
38.4.3 Results for Geometric Versions......Page 590
38.5 Future Directions......Page 591
References......Page 592
39.1 Introduction......Page 594
39.2 Dual-Fitting and Factor-Revealing LP......Page 595
39.3.1 The 1.61-Approximation Algorithm......Page 598
39.3.2 The 1.52-Approximation Algorithm......Page 599
39.4 Quasi-Greedy Algorithm for Two-Level Facility Location......Page 601
References......Page 604
40.1 Introduction......Page 606
40.2.3 The Primal-Dual Algorithm of Goemans and Williamson......Page 607
40.3.2 History of the Results......Page 610
40.3.3 A 5-Approximation Algorithm for kappa-Minimum Spanning Tree and kappa-Traveling Salesman Problem......Page 611
40.4.2 History of the Results......Page 614
Minimum Latency Problem......Page 615
40.5.3 A 3.59-Approximation Algorithm for the Minimum Latency Problem......Page 616
References......Page 617
41.1 Introduction......Page 619
41.2 Related Work......Page 620
41.3.1 Tolerating Faulty Hosts......Page 622
41.4 Performance Considerations......Page 623
41.6.2 The JICOS Branch-and-Bound Framework......Page 624
41.7.4 The Measurements......Page 626
References......Page 628
42.1 Introduction......Page 630
Minimax Theorem......Page 632
The Steiner Ratio in Banach Spaces......Page 633
42.3.2 Zelikovsky’s Idea......Page 634
42.3.4 Variable Metric Method......Page 635
42.4 Approximation for Geometric Steiner Minimum Trees......Page 636
42.4.1 Guillotine Cut......Page 637
42.4.2 m-Guillotine Subdivision......Page 638
42.4.3 Portals......Page 639
42.4.4 Comparison and Combination......Page 640
References......Page 641
43.1 Introduction......Page 644
43.2 The Greedy Triple Contraction and Batched Greedy Algorithms......Page 646
43.3 Generation of Triples......Page 649
43.4 Computing Maximum Cost Edge on a Tree Path......Page 651
43.5 Experimental Results......Page 652
Acknowledgments......Page 654
References......Page 655
44.1 Introduction......Page 657
Boolean Function Feasible (TS)......Page 659
Algorithm Largest-Optional-Processing-Time-First......Page 660
Algorithm Smallest-Optional-Processing-Time-First......Page 662
44.5 Proofs of Assertions......Page 664
44.6 Conclusions......Page 666
References......Page 667
45.1 Introduction......Page 668
45.2 A 3/2-Approximation Algorithm for IMT Scheduling......Page 670
45.3 An AFPTAS for IMT Scheduling......Page 672
45.4 An Approximation Algorithm for PCMT Scheduling with Tree Precedence......Page 675
45.5 Approximation Algorithms for PCMT Scheduling......Page 678
45.5.1 Improved Approximation Algorithm for PCMT Scheduling......Page 679
45.5.2 Approximation Algorithm for PCMT Scheduling (MT3)......Page 680
Acknowledgment......Page 681
References......Page 682
46.1 Introduction......Page 684
46.3 Vehicle Scheduling Problem......Page 685
46.3.1.1 In Trees......Page 686
46.3.1.2 In Paths......Page 688
46.3.2 Multi-Vehicle Scheduling......Page 689
References......Page 691
47.1.1 Classical Planning......Page 693
47.1.2 Methods for Solving Classical Planning Problems......Page 694
47.2 Relaxations of Classical Planning Problems......Page 696
47.2.1 Heuristic Guidance Using Relaxed Planning Problems......Page 697
47.2.2 Solution Approximations Using Relaxation......Page 699
47.2.3 Heuristic Guidance via Subproblem Identification......Page 700
47.3.2 Local Search Neighborhoods for Planning......Page 702
47.3.3 Selecting the Successor......Page 704
Acknowledgments......Page 705
References......Page 706
48.1 Introduction......Page 708
48.2.2 Related Problems and Complexity......Page 709
48.4 Local Search......Page 711
48.5 Lagrangian Relaxation......Page 713
48.6 Lagrangian Heuristics......Page 714
48.7 Metaheuristics......Page 715
48.7.1 EC Probe......Page 716
48.7.3 Algorithms TSEC and PREC......Page 717
48.8 Branch-and-Bound Algorithms......Page 718
48.9 Computational Results......Page 719
48.10 Performance Guarantee......Page 722
References......Page 723
49.1 Introduction......Page 726
Iteration (step j )......Page 727
49.2.1 Performance Bound for Maxsat Problem......Page 728
49.2.2 Performance Bound for Minsat Problem......Page 731
49.4 Conclusion......Page 733
References......Page 734
Part V: Computational Geometry and Graph Applications......Page 735
50.1 Introduction......Page 736
Properties of 3D Triangulations......Page 737
Some Triangulation Heuristics for Convex Polyhedra......Page 738
50.2 2D Minimum Weight Triangulation......Page 739
50.2.1 An O(log n) Approximation Algorithm for Point Sets......Page 741
50.2.2 A Constant Factor Approximation Algorithm for Point Sets......Page 742
50.3 2D Maximum Weight Triangulation......Page 743
Improving the Approximation Ratio to 4.238......Page 744
50.4.2 A Better Approximation Algorithm......Page 745
50.4.3 Lower Bound for Approximation Ratio......Page 746
50.4.4 Special Cases......Page 747
References......Page 748
51.1.1 Multiconnectivity Problems......Page 752
51.1.3 Overview of the Results......Page 754
51.2 Preliminaries......Page 755
51.3 First Approach: Polynomial-Time “Pseudo-Approximation” Schemes......Page 756
51.3.1.1 m-Portal-Respecting Graphs......Page 757
51.3.2 Dynamic Programming and Finding an Optimal m-Portal-Respecting r-Light Solution......Page 758
51.3.3 Patching Lemma: Reducing Number of Crossings Using Steiner Points......Page 759
51.3.4 Structure Theorem: There Is Always a Good r-Light Steiner k-VCSS......Page 760
Sketch of the proof......Page 761
51.4 PTAS for Geometric Multiconnectivity Problems......Page 762
51.4.1.1 Local Decomposition Lemma......Page 763
51.4.1.3 Filtering Lemma......Page 765
51.4.1.5 Concluding: Structure Theorem for kappa-Vertex Connectivity......Page 766
51.5 Faster PTAS for Euclidean kappa-ECSSM and 2-Connected Graphs......Page 767
51.5.1 2-Connected Graphs Are Not Worse than 2-Connected Multigraphs......Page 768
51.6 Lower Bounds......Page 769
51.7.2 Steiner kappa-Connectivity—Real Approximation Schemes......Page 770
51.7.4 Finding Low-Cost kappa-VCSS and kappa-ECSS in Planar Graphs......Page 771
References......Page 772
52.1 Introduction......Page 775
52.2 Constructing t-Spanners......Page 776
Skip-List Spanners......Page 777
52.2.2 The Well-Separated Pair Decomposition-Graph......Page 778
52.2.3 The Greedy-Graph......Page 779
52.3.1 Approximating the Dilation......Page 780
52.4.1 Structural Properties......Page 781
52.4.2 Algorithmic Questions......Page 783
52.4.3 Low Detour Embeddings of Point Sets......Page 785
Exclusion and Inclusion Regions......Page 786
52.5.2 Stars......Page 787
References......Page 788
53.1 Introduction......Page 792
53.2 Well-Separated Pairs......Page 793
53.3.1 The Split Tree......Page 794
53.4 Exact Algorithms for Proximity Problems......Page 795
53.4.2 The kappa Closest Pairs Problem......Page 796
53.4.3 The All-Nearest Neighbors Problem......Page 797
53.5.2 The Spanner Problem......Page 798
53.5.3 The Minimum Spanning Tree Problem......Page 799
53.5.4 The kappath Closest Pair Problem......Page 800
53.6 Generalization to Metric Spaces......Page 801
References......Page 803
54.1 Introduction......Page 804
54.2 A Divide-and-Conquer Algorithm......Page 805
54.3.2 Approximation Bound......Page 811
54.3.3 Improved Approximation Bound......Page 814
54.4 Concluding Remarks......Page 816
References......Page 817
55.1 Introduction......Page 818
55.2.1 Definitions and Notation......Page 819
55.3 Planar Digital Objects......Page 820
55.3.1 A General Coding Scheme......Page 821
55.3.2 Encoding by Least Squares Fit Polynomials......Page 825
55.3.3 Encoding Planar Regions......Page 827
55.4 Threshold Functions on Binary Inputs......Page 828
55.5 Concluding Remarks......Page 831
References......Page 832
56.1 Introduction......Page 833
56.2 Analysis of the MST Algorithm......Page 834
56.3 Triangular Structures and Better Approximations......Page 836
56.4 Analysis of the Triangular Structure Algorithms......Page 838
56.5 Outerplanar Subgraphs......Page 842
56.6 Practical Results and Discussion......Page 845
References......Page 846
57.1 Introduction......Page 849
57.1.1 Complexity of Disjoint-Path Problems......Page 850
57.1.3 Main Threads......Page 851
57.2.2 Greedy Algorithms......Page 853
57.3.1 Randomized Rounding and UFP......Page 855
57.3.2 Packing Integer Programs and UFP......Page 857
57.3.3 Combinatorial Algorithms and Other Results......Page 858
57.4 Variants of the Basic Problems......Page 859
References......Page 860
Generalized Steiner Network......Page 865
Small Requirements......Page 866
58.2 Preliminaries......Page 867
58.3 Edge-Covers of Set-Functions and LP-Relaxations......Page 869
Connectivity Augmentation......Page 871
58.4.2 Augmenting a kappa-Connected Graph to Be (kappa + 1)-Connected......Page 873
58.5.1 Algorithm Based on Edge-Covers......Page 876
58.5.2 LP-Rounding Algorithm for Directed Min-Size kappa-ECSS......Page 877
58.6.1 Undirected Graphs......Page 878
58.7.1 A 2-Approximation Algorithm for Undirected Edge-GSN......Page 879
58.7.2 Approximation Algorithm for kappa-CSS......Page 880
58.8 Hardness of Approximation: Three Typical Reductions......Page 881
References......Page 883
59.1 Introduction......Page 886
59.2 Minimum Routing Cost Spanning Tree......Page 887
59.2.2 Routing Loads, Separators, and General Stars......Page 888
59.2.4 A Reduction to the Metric Case......Page 890
59.2.5.1 Approximation Ratio......Page 891
59.2.5.2 Finding the Optimal kappa-Star......Page 892
59.3 Product-Requirement Communication Spanning Tree......Page 893
59.3.2 A Polynomial-Time Approximation Scheme......Page 894
59.4 Sum-Requirement Communication Spanning Tree......Page 895
59.5 Multiple Sources MRCT......Page 896
59.5.1 Approximating the 2-MRCT......Page 897
59.5.2 The Weighted 2-MRCT......Page 898
59.5.2.2 On Metric Graphs......Page 899
59.6.1.2 The p-OCT......Page 900
59.7 Concluding Remarks......Page 901
References......Page 902
60.1 Introduction......Page 903
60.1.2 Bounds on the Bisection Width......Page 904
60.2 Global Heuristics......Page 905
60.3.1 The Multilevel Scheme......Page 906
60.3.2.2 Approximation Algorithms for Cardinality Matching......Page 907
60.3.2.4 1/2-Approximation Algorithms for Maximum-Weighted Matching......Page 908
60.3.2.5 2/3 – epsilon Approximation Algorithms for Maximum-Weighted Matching......Page 910
60.3.3.1 The Kernighan–Lin Refinement Heuristic......Page 911
60.3.3.2 The Helpful-Set Refinement Heuristic......Page 912
60.3.4 Graph Partitioning Tools......Page 913
60.4 Discussion......Page 914
References......Page 915
61.1 Introduction......Page 918
61.2.2 Integrated Circuit Design......Page 920
61.3 Definitions and Terminology......Page 921
61.4 Summary of Techniques and Their Scale Dependence......Page 922
61.4.2 Branch and Bound......Page 923
61.4.5 Other Types of Algorithms......Page 924
61.5 The Fiduccia–Mattheyses Heuristic......Page 925
61.5.2 Gain Computation and Gain Update......Page 926
61.5.3 Custom Data Structures......Page 927
61.6 Multilevel Fiduccia–Mattheyses Partitioning Framework......Page 929
61.6.1 Coarsening......Page 930
61.6.3 Refinement......Page 931
61.7.1 hMETIS Benchmark Format......Page 932
Appendix: Empirical Results......Page 933
References......Page 934
62.1 Introduction......Page 937
62.2.1 Deterministic Algorithms......Page 938
62.2.1.1 Sequential Algorithm......Page 939
62.2.2.1 Randomized Optimal Solution......Page 942
62.2.2.2 Randomized Approximate Solution......Page 943
62.3.1.1 Sequential Algorithm......Page 944
62.3.1.2.2 CREW Implementation......Page 946
62.3.2 MVE with Respect to APSPs......Page 947
62.3.2.1 Sequential Algorithm......Page 948
62.3.2.2.1 CRCW Implementation......Page 949
References......Page 950
63.1 Introduction......Page 953
63.2 Benchmark Instances......Page 954
63.3 Preprocessing and Heuristic Reduction Rules......Page 955
63.4 Construction Heuristics......Page 956
63.5.1 Strategy 1: kappa Fixed, Complete Colorings......Page 957
63.5.3 Strategy 3: kappa Variable, Complete Colorings......Page 958
63.5.4 Neighbourhood Examination and Data Structures......Page 959
63.6.1 Strategy 1: kappa Fixed, Complete Colorings......Page 960
63.7 Experimental Comparison of Stochastic Local Search Algorithms......Page 962
Acknowledgments......Page 966
References......Page 967
64.1 Introduction......Page 970
64.2 A Greedy Approach......Page 971
64.2.1 An Example where SGA and the Multistart Greedy Algorithm Fail......Page 972
64.3 An Ant Colony Optimization Approach......Page 973
64.3.2 Algorithmic Framework......Page 974
64.3.2.1 Solution Construction......Page 976
64.3.2.3 Escape Mechanism......Page 978
64.4 Experiments......Page 979
64.4.1 Problem Instances......Page 980
64.4.2 Experiments and Results......Page 981
Acknowledgments......Page 983
References......Page 984
Part VI: Large-Scale and Emerging Applications......Page 986
65.1 Introduction......Page 987
65.2 Multicast Routing in Ad Hoc Networks......Page 988
65.3.1 Problem Formulation......Page 990
65.3.2 NP-Completeness......Page 991
65.3.3.1 Greedy-Based Heuristic Algorithm......Page 992
65.3.3.2 Distributed Variant......Page 993
65.3.4.1 Performance Analysis......Page 994
65.4.1 The Cost over Progress Framework......Page 996
65.4.2 Geographic Multicasting with Cost over Progress......Page 997
65.4.2.2 Greedy Selection of Set Partitions......Page 998
References......Page 999
66.1 Introduction......Page 1001
66.2 Motivation......Page 1002
66.3 Technicalities......Page 1004
66.4 Our Tree-Based Clustering Algorithm......Page 1005
66.4.1 The Tree-Based Cluster Split Algorithm: Single-Link Failure......Page 1006
66.4.2 The Tree-Based Cluster Split Algorithm: Single-Node Failure......Page 1007
66.4.3 Merging Clusters......Page 1008
66.5.1 Performance Metrics......Page 1009
66.5.2 Simulation Results......Page 1010
66.6 Application......Page 1013
66.7 Concluding Remarks......Page 1014
References......Page 1015
67.1 Introduction......Page 1016
67.2.2 Notation for Topology Control Problems......Page 1017
67.3.1 A General Framework......Page 1018
67.3.2.2 An Approximation Algorithm for (UNDIR, 2-NODE-CONNECTED, TOTALP)......Page 1020
Proof of Lemma 67.1......Page 1022
67.3.2.3 An Approximation Algorithm for (UNDIR, 2-EDGE-CONNECTED, TOTALP)......Page 1023
67.3.2.4 Improvement by Calinescu and Wan......Page 1024
Minimum Cost Tree with a Diameter Constraint......Page 1026
67.3.4 Distributed Approximation Algorithms......Page 1029
67.3.4.2 Distributed Algorithms for (GEOMETRIC, 2-NODE-CONNECTED, TOTALP)......Page 1030
Proof of Theorem 67.9......Page 1031
67.4 A Summary of Results for Other Topology Control Problems......Page 1032
Acknowledgments......Page 1033
References......Page 1034
68.1.1 Geometrical Spanner......Page 1036
68.1.4 Efficient Localized Construction......Page 1037
68.2.1 Relative Neighborhood Graph......Page 1038
68.2.4 Local Delaunay Graph......Page 1039
68.3 Bounded-Degree Spanner and Yao’s Family......Page 1040
68.3.3 Sparsified Yao......Page 1041
68.3.5 Ordered Yao......Page 1042
68.4.1 Delaunay Triangulation Plus Yao Structure......Page 1043
68.4.2 Local Delaunay Graph Plus Yao Structure......Page 1044
68.4.3 Gabriel Graph Plus Yao Structure......Page 1045
68.5 Other Spanners......Page 1046
References......Page 1047
69.1 Introduction......Page 1051
69.2 Mathematical Models of Multicast Network......Page 1052
69.3.1 Existing Approach for Siblings Classification......Page 1054
69.3.2 Hamming Distance Classification Approach......Page 1055
69.3.3 Binary Hamming Distance Classification Algorithm......Page 1056
69.3.4 Analysis on Inference Accuracy of Hamming Distance Classification Approach.......Page 1057
69.3.5 Experimental Results for Topology Inference......Page 1059
69.4 Hamming Distance Matrix for Internal Loss/Delay Performance Analysis......Page 1061
69.5 Topology Inference for General Trees......Page 1062
References......Page 1063
70.1 Introduction......Page 1065
70.2 The Undirected MCHEC Problem......Page 1067
70.2.1 The Re-Embedding Algorithm......Page 1068
70.2.2 The Clockwise (2/3)-Rounding Algorithm......Page 1069
70.2.3 The Randomized Rounding Algorithm......Page 1071
70.3 The Directed MCHEC Problem......Page 1072
References......Page 1074
71.1 Introduction......Page 1076
71.2 Centralized Approximation Algorithms......Page 1077
71.2.2 The Charikar–Naor–Schieber Algorithms......Page 1078
71.2.3 Beta-Convex Steiner Tree Approximation Algorithms......Page 1079
71.2.4 Beta-Convex Approximation for QoSMT with Two Rates......Page 1081
71.2.5 Beta-Convex Approximation for QoSMT with Unbounded Number of Rates......Page 1083
71.3.1 A Simple Integer Linear Program (ILP) Formulation......Page 1085
71.3.2 Two Primal-Dual Methods for the Simple ILP Formulation......Page 1086
71.3.3 Primal-Dual 4.311-Approximation Algorithm......Page 1087
71.4 Experimental Study......Page 1089
References......Page 1091
72.1 Introduction......Page 1092
72.2.1 The Hierarchical Decomposition Technique......Page 1093
72.2.3 The Prefix Technique......Page 1095
72.3 Supervised Overlay Networks......Page 1096
72.3.2 Putting the Pieces Together......Page 1097
72.3.3 Maintaining Condition 72.6......Page 1098
72.4.1.1 Maintaining a Dynamic Hypercube......Page 1099
72.4.1.2 Maintaining a Dynamic deBruijn Graph......Page 1100
72.4.2 Overlay Networks Based on Prefix Connections......Page 1101
72.4.2.1 The PRR Scheme......Page 1102
72.4.2.1.1 Prefix Routing......Page 1103
72.4.2.1.2 Route, Join, and Leave......Page 1104
72.4.2.2 The LAND Scheme......Page 1105
72.5 Other Related Work......Page 1106
References......Page 1107
73.1 Introduction......Page 1109
73.2 Problem Formulation......Page 1111
73.3 Uniform Lengths......Page 1112
73.3.2 The Dichotomic Algorithm......Page 1113
73.3.3 Two Channels......Page 1115
73.4 Nonuniform Lengths......Page 1116
73.5.1 The Greedy Algorithm......Page 1118
73.5.3 The Dlinear Algorithm......Page 1119
73.6 Experimental Tests......Page 1120
73.7 Conclusions......Page 1122
References......Page 1123
74.1 Introduction......Page 1125
74.3.1 Fixed-Parameter Tractability......Page 1126
74.4 A Biclique-Oriented Approach......Page 1127
74.4.3 Reduction Rules for the (alpha, beta) - kappa-Feature Set Problem......Page 1129
74.5 A Hamiltonian Path-Motivated Approach for Gene Ordering......Page 1130
74.6 Computational Experiments and Results......Page 1132
References......Page 1135
75.1.1 Background Information......Page 1139
75.1.2 Polymerase Chain Reaction......Page 1140
75.1.3 Terminology......Page 1141
75.1.4 NP-Completeness of Primer Selection Problem and Degenerate Primer Selection Problem......Page 1142
75.1.5 Algorithms for PSP......Page 1143
75.1.6.1 Algorithm HYDEN......Page 1144
75.1.6.2 Algorithm DePiCt......Page 1145
75.1.6.3 Algorithm Multiple Iterative Primer Selector......Page 1146
75.1.6.4 Algorithm Degenerate Primer Search (DPS)......Page 1147
75.2 The Planted Motif Search Problem......Page 1148
75.2.3 Algorithm PMS1......Page 1149
75.3.1 The Closest String Problem......Page 1150
75.3.1.2 An Approximate Solution Using Integer Programming......Page 1151
75.3.1.3 A (1 + epsilon) Polynomial-Approximate Scheme......Page 1153
75.3.2.1 Simple Approximation Schemes......Page 1157
75.3.2.2 A (1 + epsilon) Polynomial-Approximation Scheme......Page 1159
References......Page 1161
76.1 Introduction......Page 1164
76.2 Framework for Pairwise Sequence Comparison......Page 1166
76.3 Fractional Programming ANLA Algorithms......Page 1167
76.4 Approximation Algorithms for Partial Constraint Satisfaction......Page 1170
76.5 Normalized Local Alignment......Page 1175
76.6 Discussion......Page 1177
References......Page 1178
77.1.1 Single Nucleotide Polymorphisms and Haplotypes......Page 1179
77.1.2 Haplotype Blocks and Tag SNPs......Page 1180
77.1.3 The Problem of Missing Data......Page 1181
77.2 Finding Robust Tag SNPs......Page 1182
Problem: Minimum Robust Tag SNPs......Page 1183
77.2.1 The First Greedy Algorithm......Page 1184
77.2.2 The Second Greedy Algorithm......Page 1186
77.2.3 The Iterative LP-Relaxation Algorithm......Page 1188
Problem: Minimum Auxiliary Tag SNPs......Page 1190
77.4.1 Results on Simulated Data......Page 1191
77.4.2 Results on Biological Data......Page 1192
77.4.3 Discussion......Page 1193
References......Page 1194
78.1 Introduction......Page 1196
78.2 Preliminaries......Page 1198
78.3.1 2-D Lattice Packing with Translation......Page 1199
78.3.2 2-D Lattice Packing with Translation and Rotation......Page 1201
78.3.3 Shaking a Lattice Packing......Page 1203
78.4 Trimming and Packing......Page 1204
78.5 Extensions to Three or Higher Dimensions......Page 1205
78.7 Experimental Studies......Page 1206
References......Page 1207
79.1 Background......Page 1210
79.1.1 Mathematical Formulation......Page 1211
79.2.1.1 Iterative Improvement over Feasible Placements......Page 1213
79.2.1.2 Iterative Improvement over Infeasible Placements......Page 1214
79.2.3.1 Cutsize Minimization......Page 1215
79.2.3.2 Partitions Guided by Analytical Placements......Page 1217
79.2.4 Multiscale Methods......Page 1218
79.2.4.1 Coarsening......Page 1219
Example: APlace......Page 1220
Comparison to APlace......Page 1221
79.3.1 Timing......Page 1222
79.4 Conclusion......Page 1223
References......Page 1224
80.1 Introduction......Page 1229
80.2 Problem Formulation......Page 1230
Integrated Global Routing and Bounded Wireload Buffer Insertion Problem......Page 1231
80.3.1 Gadget Graph and Integer Program Formulation......Page 1232
80.3.2 The Approximation Algorithm......Page 1234
80.3.4 Area and Congestion Trade-Off Curve......Page 1236
80.4 Handling Multipin Nets......Page 1237
80.5.2 Polarity Constraints......Page 1239
80.5.4 Delay Constraints......Page 1240
80.6 Experimental Results......Page 1242
80.7 Conclusions......Page 1245
References......Page 1246
81.1 Introduction......Page 1247
81.1.1 Selfish Tasks: The KP and CKN Models......Page 1248
81.2.1 Price of Anarchy for the KP Model......Page 1249
81.2.2 Coordination Mechanisms for the CKN Model......Page 1252
81.3.1 Approximate Stability for the CKN Model......Page 1253
81.4 Truthful Algorithms......Page 1255
81.4.1 Truthful Algorithm for Scheduling Selfish Tasks......Page 1256
81.4.2.1 Monotonicity......Page 1258
81.4.2.2 A Truthful Algorithm for the AT Model......Page 1259
Pure Equilibria......Page 1262
Coordination Mechanisms......Page 1263
81.5.3 Results for the AT Model......Page 1264
References......Page 1265
82.1 Introduction......Page 1267
82.2 Models and Definitions......Page 1268
82.3.1 A Convex Formulation for a Class of General Equilibrium Model......Page 1270
82.3.2 Homogeneous Utility Functions......Page 1272
82.4 Ellipsoid Algorithm......Page 1274
82.5 Approximation Algorithm for Indivisible Goods......Page 1277
82.6 Hardness Results......Page 1279
References......Page 1282
83.1 Introduction......Page 1285
83.2.1 Approximation Algorithms......Page 1286
83.2.2 Algorithm Mechanism Design......Page 1287
83.2.3 Binary Demand Games and General Demand Games......Page 1288
83.3.1 Untruthfulness of VCG Mechanism: An Example......Page 1289
83.3.2 Untruthfulness of VCG Mechanism: General Results......Page 1290
83.4.1 Characterize the Strategyproof Mechanism......Page 1291
83.4.2 Simple Composition Technique......Page 1292
83.4.3 Complex Composition Technique......Page 1294
83.5.1 Characterize the Strategyproof Mechanism......Page 1297
83.5.2 DiffServ Multicast Game......Page 1298
83.6 Literature Review......Page 1300
83.7 Conclusion......Page 1301
References......Page 1302
84.1 Introduction......Page 1304
84.2 Definitions and Problems......Page 1305
84.3.1 The Vopt or the … Measure......Page 1307
84.3.2 Beyond … Error: Workloads, Piecewise Polynomials......Page 1310
84.3.3 … and Variants......Page 1311
84.4.1 A Compact Primer on Compact Wavelets......Page 1313
84.4.2 Wavelet Synopses and … Theory......Page 1314
84.4.3.1 Streaming PTAS for Haar Systems......Page 1315
84.4.4 Restricted Optimizations......Page 1316
84.5 From (Haar) Wavelets Form Histograms......Page 1317
Notes......Page 1318
References......Page 1320
85.1 Introduction......Page 1322
85.2 Applications of Reputation Management......Page 1323
85.3 Motivating Cooperation......Page 1325
85.4 Design Requirements for a Reputation System......Page 1326
85.5.1 Direct versus Indirect Evidence......Page 1327
85.5.2 Second-Order Reputation......Page 1328
85.5.4 Motivation Is Not a Problem: Dissenting Views......Page 1329
85.5.5 Other Design Issues......Page 1330
85.6.1 Complaints-Based Trust......Page 1331
85.6.2 EigenTrust......Page 1332
85.6.4 ROCQ......Page 1334
85.7 Conclusions and Future Work......Page 1335
References......Page 1336
86.1 Introduction......Page 1338
86.2 Color Spaces for Quantization......Page 1340
86.3 Image-Independent Quantization......Page 1341
86.4 Image-Dependent, Context-Free Quantization......Page 1343
86.5.2 Feedback-Based Quantization......Page 1349
References......Page 1353