Paradigms of Combinatorial Optimization E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 1405

Veröffentlichungsjahr: 2013

Beschreibung

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management.
The three volumes of the Combinatorial Optimization series aims to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization.

“Paradigms of Combinatorial Optimization” is divided in two parts:
• Paradigmatic Problems, that handles several famous combinatorial optimization problems as max cut, min coloring, optimal satisfiability tsp, etc., the study of which has largely contributed to both the development, the legitimization and the establishment of the Combinatorial Optimization as one of the most active actual scientific domains;
• Classical and New Approaches, that presents the several methodological approaches that fertilize and are fertilized by Combinatorial optimization such as: Polynomial Approximation, Online Computation, Robustness, etc., and, more recently, Algorithmic Game Theory.

Leseprobe

Table of Contents

Preface

PART I: Paradigmatic Problems

Chapter 1: Optimal Satisfiability

1.1. Introduction

1.2. Preliminaries

1.3. Complexity of decision problems

1.4. Complexity and approximation of optimization problems

1.5. Particular instances of constraint satisfaction problems

1.6. Satisfiability problems under global constraints

1.7. Conclusion

1.8. Bibliography

Chapter 2: Scheduling Problems

2.1. Introduction

2.2. New techniques for approximation

2.3. Constraints and scheduling

2.4. Non-regular criteria

2.5. Bibliography

Chapter 3: Location Problems

3.1. Introduction

3.2. Continuous problems

3.3. Discrete problems

3.4. On-line problems

3.5. The quadratic assignment problem

3.6. Conclusion

3.7. Bibliography

Chapter 4: MiniMax Algorithms and Games

4.1. Introduction

4.2. Games of no chance: the simple cases

4.3. The case of complex no chance games

4.4. Quiescence search

4.5. Case of games using chance

4.6. Conclusion

4.7. Bibliography

Chapter 5: Two-dimensional Bin Packing Problems

5.1. Introduction

5.2. Models

5.3. Upper bounds

5.4. Lower bounds

5.5. Exact algorithms

5.6. Acknowledgments

5.7. Bibliography

Chapter 6: The Maximum Cut Problem

6.1. Introduction

6.2. Complexity and polynomial cases

6.3. Applications

6.4. The cut polytope

6.5. Semi-definite programming (SDP) and the maximum cut problem

6.6. The cut cone and applications

6.7. Approximation methods

6.8. Related problems

6.9. Conclusion

6.10. Bibliography

Chapter 7: The Traveling Salesman Problem and its Variations

7.1. Introduction

7.2. Elementary properties and various subproblems

7.3. Exact solving algorithms

7.4. Approximation algorithm for max TSP

7.5. Approximation algorithm for min TSP

7.6. Constructive algorithms

7.7. Conclusion

7.8. Bibliography

Chapter 8: 0–1 Knapsack Problems

8.1. General solution principle

8.2. Relaxation

8.3. Heuristic

8.4. Variable fixing

8.5. Dynamic programming

8.6. Solution search by hybridization of branch-and-bound and dynamic programming

8.7. Conclusion

8.8. Bibliography

Chapter 9: Integer Quadratic Knapsack Problems

9.1. Introduction

9.2. Solution methods

9.3. Numerical experiments

9.4. Conclusion

9.5. Bibliography

Chapter 10: Graph Coloring Problems

10.1. Basic notions of colorings

10.2. Complexity of coloring

10.3. Sequential methods of coloring

10.4. An exact coloring algorithm

10.5. Tabu search

10.6. Perfect graphs

10.7. Chromatic scheduling

10.8. Interval coloring

10.9. T-colorings

10.10. List colorings

10.11. Coloring with cardinality constraints

10.12. Other extensions

10.13. Edge coloring

10.14. Conclusion

10.15. Bibliography

PART II: New Approaches

Chapter 11: Polynomial Approximation

11.1. What is polynomial approximation?

11.2. Some first examples of analysis: constant approximation ratios

11.3. Approximation schemes

11.4. Analyses depending on the instance

11.5. Conclusion: methods and issues of approximation

11.6. Bibliography

Chapter 12: Approximation Preserving Reductions

12.1. Introduction

12.2. Strict and continuous reductions

12.3. AP-reduction and completeness in the classes NPO and APX

12.4. L-reduction and completeness in the classes Max-SNP and APX

12.5. Affine reduction

12.6. A few words on GAP-reduction

12.7. History and comments

12.8. Bibliography

Chapter 13: Inapproximability of Combinatorial Optimization Problems

13.1. Introduction

13.2. Some technical preliminaries

13.3. Probabilistically checkable proofs

13.4. Basic reductions

13.5. Optimized reductions and PCP constructions

13.6. An overview of known inapproximabiity results

13.7. Integrality gap results

13.8. Other topics

13.9. Conclusions

13.10. Prove optimal results for 2-query PCPs

13.11. Settle the Unique Games Conjecture

13.12. Prove a strong inapproximabiity result for Metric TSP

13.13. Acknowledgements

13.14. Bibliography

Chapter 14: Local Search: Complexity and Approximation

14.1. Introduction

14.2. Formal framework

14.3. A few familiar optimization problems and their neighborhoods

14.4. The PLS class

14.5. Complexity of the standard local search algorithm

14.6. The quality of local optima

14.7. Approximation results

14.8. Conclusion and open problems

14.9. Bibliography

Chapter 15: On-line Algorithms

15.1. Introduction

15.2. Some classical on-line problems

15.3. Competitive analysis of deterministic algorithms

15.4. Randomization

15.5. Extensions of competitive analysis

15.6. Bibliography

Chapter 16: Polynomial Approximation for Multicriteria Combinatorial Optimization Problems

16.1. Introduction

16.2. Presentation of multicriteria combinatorial problems

16.3. Polynomial approximation and performance guarantee

16.4. Bibliographical notes

16.5. Conclusion

16.6. Bibliography

Chapter 17: An Introduction to Inverse Combinatorial Problems

17.1. Introduction

17.2. Definitions and notation

17.3. Polynomial inverse problems and solution techniques

17.4. Hard inverse problems

17.5. Conclusion

17.6. Bibliography

Chapter 18: Probabilistic Combinatorial Optimization

18.1. Motivations and applications

18.2. The issues: formalism and methodology

18.3. Problem complexity

18.4. Solving problems

18.5. Approximation

18.6. Bibliography

Chapter 19: Robust Shortest Path Problems

19.1. Introduction

19.2. Taking uncertainty into account: the various models

19.3. Measures of robustness

19.4. Complexity and solution of robust shortest path problems in the interval model

19.5. Complexity and solution of robust shortest path problems in a discrete set of scenarios model

19.6. Conclusion

19.7. Bibliography

Chapter 20: Algorithmic Games

20.1. Preliminaries

20.2. Nash equilibria

20.3. Mixed extension of a game and Nash equilibria

20.4. Algorithmic problems

20.5. Potential games

20.6. Congestion games

20.7. Final notes

20.8. Bibliography

List of Authors

Index

First published in Great Britain and the United States in 2010 by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from Optimisation combinatoire volumes 1 to 5 published 2005-2007 in France by Hermes Science/Lavoisier © LAVOISIER 2005, 2006, 2007

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUKJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.wiley.com

© ISTE Ltd 2010

The rights of Vangelis Th. Paschos to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Combinatorial optimization / edited by Vangelis Th. Paschos.

v. cm.

Includes bibliographical references and index.

Contents: v. 1. Concepts of combinatorial optimization

ISBN 978-1-84821-146-9 (set of 3 vols.)

-- ISBN 978-1-84821-148-3 (v. 2)

1. Combinatorial optimization. 2. Programming (Mathematics)

I. Paschos, Vangelis Th.

QA402.5.C545123 2010

519.6′4--dc22

2010018423

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-146-9 (Set of 3 volumes)

ISBN 978-1-84821-148-3 (Volume 2)

Preface

Paradigms of Combinatorial Optimization is the second volume of the Combinatorial Optimization series. It deals with advanced concepts as well as a series of problems, studies and research which have made, and continue to make, their mark on the evolution of this discipline. This work is divided into two parts:

– Part I: Paradigmatic Problems;

– Part II: New Approaches.

Part I contains the following chapters:

– Optimal Satisfiability by Cristina Bazgan;

– Scheduling Problems by Philippe Chrétienne and Christophe Picouleau;

– Location Problems by Aristotelis Giannakos;

– MinMax Algorithms and Games by Michel Koskas;

– Two-dimensional Bin Packing Problems by Andrea Lodi, Silvano Martello, Michele Monaci and Daniele Vigo;

– The Maximum Cut Problem by Walid Ben-Ameur, Ali Ridha Mahjoub and José Neto;

– The Traveling Salesman Problem and its Variations by Jérôme Monnot and Sophie Toulouse;

– 0–1 Knapsack Problems by Gérard Plateau and Anass Nagih;

– Integer Quadratic Knapsack Problems by Dominique Quadri, Eric Soutif and Pierre Tolla;

– Graph Coloring Problems by Dominique De Werra and Daniel Kobler.

All these chapters not only deal with the problems in question, but also highlight various tools and methods from combinatorial optimization and operations research. Obviously, this list is very limited and does not pretend to cover all the flagship problems in combinatorial optimization.

It is best to view the problems in this book as a sample that testifies to the richness of the themes and problems that can be tackled by combinatorial optimization, and of the tools developed by this discipline.

Part II includes the following chapters:

– Polynomial Approximation by Marc Demange and Vangelis Th. Paschos;

– Approximation Preserving Reductions by Giorgio Ausiello and Vangelis Th. Paschos;

– Inapproximability of Combinatorial Optimization Problems by Luca Trevisan;

– Local Search: Complexity and Approximation by Eric Angel, Petros Christopoulos and Vassilis Zissimopoulos;

– On-line Algorithms by Giorgio Ausiello and Luca Becchetti;

– Polynomial Approximation for Multicriteria Combinatorial Optimization Problems by Eric Angel, Evripidis Bampis and Laurent Gourvès;

– An Introduction to Inverse Combinatorial Problems by Marc Demange and Jérôme Monnot;

– Probabilistic Combinatorial Optimization by Cécile Murat and Vangelis Th. Paschos;

– Robust Shortest Path Problems by Virginie Gabrel and Cécile Murat;

– Algorithmic Games by Aristotelis Giannakos and Vangelis Th. Paschos.

The themes of this part are at the border between research operations and combinatorial optimization, theoretical computer science and discrete mathematics. Nevertheless, all these subjects have their rightful place in the vast scientific field that we call combinatorial optimization. They are developed, at least in part, at the heart of this discipline, fertilize it, widen its renown, and enrich its models.

For this volume, my thanks go firstly to the authors who have agreed to participate in the book. This work could never have come into being without the original proposal of Jean-Charles Pomerol, Vice President of the scientific committee at Hermes, and Sami Ménascé and Raphaël Ménascé, the heads of publications at ISTE. I give my warmest thanks to them for their insistence and encouragement. It is a pleasure to work with them as well as with Rupert Heywood who has ingeniously translated this book’s material from the original French.

Vangelis Th. PASCHOS

June 2010

PART I

Paradigmatic Problems