Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives

Cover......Page 1
Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives......Page 4
Copyright......Page 5
Contents......Page 6
1.1. Introduction......Page 24
1.2. Problem......Page 26
1.3. Problem......Page 29
1.4. Problem......Page 30
1.5. Bibliography......Page 36
2.1. Introduction......Page 38
2.2. Overview......Page 40
2.3. The bicriteria......Page 41
2.4.......Page 56
2.5. Conclusion......Page 68
2.6. Bibliography......Page 69
3.1. Introduction......Page 72
3.2. Description of the main results and related work......Page 74
3.3. The price of ignorance......Page 77
3.4. Competitiveness of......Page 78
3.5. The nasty aw of greediness......Page 80
3.6. The power of look-ahead......Page 83
3.7. The maximum budget saving problem......Page 89
3.9. Bibliography......Page 92
4.1. Introduction Petri nets with time.......Page 94
4.2. Time Petri nets and timed automata Notations.......Page 96
4.3. Comparison of semantics......Page 105
4.4. Strict ordering results......Page 112
4.5. Equivalence with respect to timed language acceptance......Page 114
4.6. Bisimulation of TA by TPNs......Page 123
4.7. Conclusion......Page 143
4.8. Bibliography......Page 144
5.1. Introduction......Page 146
5.2. Approximation algorithm for the general problem......Page 148
5.3. The tree case......Page 151
5.4. Exponential algorithms for special cases......Page 157
5.5. Bibliography......Page 160
6.1. Introduction......Page 162
6.2. The patrolling task......Page 163
6.3. Previous work......Page 165
6.4. The cyclic strategies......Page 166
6.5. Partition-based strategies......Page 170
6.6. Experiments......Page 172
6.7. Conclusion......Page 173
6.8. Bibliography......Page 175
7.1. Introduction......Page 176
7.2. Myopic negotiation over indivisible resources......Page 178
7.3. Convergence for restricted classes of utility functions......Page 181
7.4. Modular utility functions and variants......Page 183
7.5. Suf cient classes of utility functions......Page 185
7.6. Necessity issues......Page 186
7.7. Maximal classes of utility functions......Page 192
7.8. Conclusion......Page 199
7.9. Bibliography......Page 200
-hard Problems......Page 204
8.1.......Page 205
8.2. Pruning the search tree by dominance conditions: the case of......Page 212
8.3. A more careful analysis for pruning: the case of......Page 227
8.4. Bibliography......Page 240
9.1. Introduction......Page 242
9.2. De nitions and notations......Page 244
9.3. Bounds for the permutation graph in a left-to-right model......Page 246
9.4. Bounds for overlap graphs......Page 250
9.5. Bounds for permutation graphs in a more general model......Page 253
9.7. Bibliography......Page 257
10.1. Introduction......Page 260
10.2. General results 10.2.1.......Page 263
10.3. Weighted node coloring in triangle-free planar graphs......Page 271
10.4. Weighted node coloring in bipartite graphs......Page 274
10.5. Split graphs......Page 281
10.6. Cographs......Page 285
10.7. Interval graphs......Page 286
10.8. Bibliography......Page 287
11.1. Introduction......Page 292
11.2. Related problems......Page 294
11.3. Preliminaries and notation......Page 295
11.4. Complexity and (in)approximability......Page 296
11.5. Graphs of......Page 297
11.6. A......Page 299
11.7. Bipartite graphs......Page 300
11.8. Trees......Page 311
11.10. Bibliography......Page 316
12.1. Introduction......Page 320
12.2. Different formulations for the daily satellite mission planning problem 12.2.1.......Page 321
12.3. Model comparison......Page 325
12.4. Experiments and results......Page 327
12.5. Conclusion......Page 328
12.6. Bibliography......Page 329
13.1. Introduction......Page 330
13.2. The Dantzig-Wolfe decomposition in 0-1 linear programming......Page 331
13.3. The stable set problem with additional linear constraints......Page 334
13.4. Dantzig-Wolfe decomposition on stable set constraints: strengthening the LP-relaxation 13.4.1.......Page 335
13.5. Conclusion......Page 338
13.6. Bibliography......Page 339
Algorithmic Games......Page 340
14.1. Preliminaries 14.1.1.......Page 341
14.2. Nash equilibria......Page 346
14.3. Mixed extension of a game and Nash equilibria......Page 348
14.4. Algorithmic problems......Page 349
14.5. Potential games......Page 356
14.6. Congestion games 14.6.1.......Page 361
14.8. Bibliography......Page 369
15.1. Introduction......Page 374
15.2. De nitions and notations......Page 375
15.3. Presentation of radix trees......Page 376
15.4. Shortest path problem......Page 381
15.5. The ow problem......Page 389
15.6. Conclusion......Page 391
15.7. Bibliography......Page 392
16.1. Introduction......Page 394
16.2. Preliminary observations......Page 398
16.3. Hardness results......Page 400
16.4. Polynomial results......Page 406
16.5. Conclusion......Page 429
16.6. Bibliography......Page 430
17.1. Introduction......Page 434
17.2. The 2-regular bipartite case......Page 437
17.3. Some inapproximation results......Page 439
17.4. The complete bipartite case......Page 447
17.5. Bibliography......Page 453
18.1. Introduction......Page 456
18.2. Complexity of......Page 461
18.3. Approximating M......Page 467
18.4. Standard and differential approximation of......Page 476
18.5. Conclusion......Page 492
18.6. Bibliography......Page 493
19.1. Introduction......Page 496
19.2. The algorithm of Djerdjour......Page 498
19.3. Improving the upper bound......Page 499
19.5. Computational results......Page 501
19.6. Conclusion......Page 504
19.7. Bibliography......Page 505