Probabilistic Combinatorial Optimization on Graphs E-Book

Cécile Murat

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

Seitenzahl: 416

Veröffentlichungsjahr: 2013

Beschreibung

This title provides a comprehensive survey over the subject of probabilistic combinatorial optimization, discussing probabilistic versions of some of the most paradigmatic combinatorial problems on graphs, such as the maximum independent set, the minimum vertex covering, the longest path and the minimum coloring. Those who possess a sound knowledge of the subject mater will find the title of great interest, but those who have only some mathematical familiarity and knowledge about complexity and approximation theory will also find it an accessible and informative read.

Leseprobe

Table of Contents

Preface

Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization

1.1. Motivations and applications

1.2. A formalism for probabilistic combinatorial optimization

1.3. The main methodological issues dealing with probabilistic combinatorial optimization

1.4. Miscellaneous and bibliographic notes

FIRST PART. Probabilistic Graph-problems

Chapter 2. The Probabilistic Maximum Independent Set

2.1. The modification strategies and a preliminary result

2.2. PROBABILISTIC MAX INDEPENDENT SET1

2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3

2.4. PROBABILISTIC MAX INDEPENDENT SET4

2.5. PROBABILISTIC MAX INDEPENDENT SET5

2.6. Summary of the results

2.7. Methodological questions

2.8. Proofs of the results

Chapter 3. The Probabilistic Minimum Vertex Cover

3.1. The strategies M1, M2 and M3 and a general preliminary result

3.2. PROBABILISTIC MIN VERTEX COVER1

3.3. PROBABILISTIC MIN VERTEX COVER2

3.4. PROBABILISTIC MIN VERTEX COVER3

3.5. Some methodological questions

3.6. Proofs of the results

Chapter 4. The Probabilistic Longest Path

4.1. Probabilistic longest path in terms of vertices

4.2. Probabilistic longest path in terms of arcs

4.3. Why the strategies used are pertinent

4.4. Proofs of the results

Chapter 5. Probabilistic Minimum Coloring

5.1. The functional E(G, C)

5.2. Basic properties of probabilistic coloring

5.3. PROBABILISTIC MIN COLORING in general graphs

5.4. PROBABILISTIC MIN COLORING in bipartite graphs

5.5. Complements of bipartite graphs

5.6. Split graphs

5.7. Determining the best k-coloring in k-colorable graphs

5.8. Comments and open problems

5.9. Proofs of the different results

SECOND PART. Structural Results

Chapter 6. Classification of Probabilistic Graph-problems

6.1. When MS is feasible

6.2. When application of MS itself does not lead to feasible solutions

6.3. Some comments

6.4. Proof of Theorem 6.4

Chapter 7. A Compendium of Probabilistic NPO Problems on Graphs

7.1. Covering and partitioning

7.2. Subgraphs and supergraphs

7.3. Iso- and other morphisms

7.4. Cuts and connectivity

Appendix A. Mathematical Preliminaries

A.1. Sets, relations and functions

A.2. Basic concepts from graph-theory

A.3. Elements from discrete probabilities

Appendix B. Elements of the Complexity and the Approximation Theory

B.1. Problem, algorithm, complexity

B.2. Some notorious complexity classes

B.3. Reductions and NP-completeness

B.4. Approximation of NP-hard problems

Bibliography

Index

First published in Great Britain and the United States in 2006 by ISTE Ltd

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 LtdISTE USA6 Fitzroy Square4308 Patrice RoadLondon W1T 5DXNewport Beach, CA 92663UKUSA

www.iste.co.uk

© ISTE Ltd, 2006

The rights of Cécile Murat and Vangelis Th. Paschos to be identified as the authors of this work has been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Murat, Cecile.

Probabilistic combinatorial optimization on graphs / Cécile Murat and Vangelis Th. Paschos.

p. cm.

Includes bibliographical references and index.

ISBN-13: 978-1-905209-33-0

ISBN-10: 1-905209-33-9

1. Combinatorial probabilities. 2. Combinatorial optimization. 3. Random graphs. I. Paschos, Vangelis Th. II. Title.

QA273.45.M87 2006

519.2--dc22

2006000868

British Library Cataloguing-in-Publication Data

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

ISBN 10: 1-905209-33-9

ISBN 13: 978-1-905209-33-0

Preface

This monograph is the outcome of our work on probabilistic combinatorial optimization since 1994. The first time we heard about it, it seemed to us to be a quite strange scientific area, mainly because randomness in graphs is traditionally expressed by considering probabilities on the edges rather than on the vertices. This strangeness was our first motivation to deal with probabilistic combinatorial optimization. As our study progressed, we have discovered nice mathematical problems, connections with other domains of combinatorial optimization and of theoretical computer science, as well as powerful ways to model real-world situations in terms of graphs, by representing reality much more faithfully than if we do not use probabilities on the basic data describing them, i.e., the vertices.

What is probabilistic combinatorial optimization? Basically, it is a way to deal with aspects of robustness in combinatorial optimization. The basic problematic is the following. We are given a graph (let us denote it by G(V, E), where V is the set of its points, called vertices, and E is a set of straight lines, called edges, linking some pairs of vertices in V), on which we have to solve some optimization problem П. But, for some reasons depending on the reality modelled by G, П is only going to be solved for some subgraph G′ of G (determined by the vertices that will finally be present) rather than for the whole of G. The measure of how likely it is that a vertex viV will belong to G′ (i.e., will be present for the final optimization) is expressed by a probability pi associated with vi. How we can proceed in order to solve П under this kind of uncertainty?

A first very natural idea that comes to mind is that one waits until G′ is specified (i.e., it is present and ready for optimization) and, at this time, one solves П in G′. This is what is called re-optimization. But what if there remains very little time for such a computation? We arrive here at the basic problematic of the book. If there is no time for re-optimization, another way to proceed is the following. One solves П in the whole of G in order to get a feasible solution (denoted by S), called a priori solution, which will serve her/him as a kind of benchmark for the solution on the effectively present subgraph G′. One has also to be provided with an algorithm that modifies S in order to fit G′. This algorithm is called modification strategy (let us denote it by M). The objective now becomes to compute an a priori solution that, when modified by M, remains “good” for any subgraph of G (if this subgraph is the one where П will be finally solved). This amounts to computing a solution that optimizes a kind of expectation of the size of the modification of S over all the possible subgraphs of G, i.e., the sum of the products of the probability that G′ is the finally present graph multiplied by the value of the modification of S in order to fit G′ over any subgraph G′ of G. This expectation, depending on both the instance of the deterministic problem П, the vertex-probabilities, and the modification strategy adopted, will be called the functional. Obviously, the presence-probability of G′ is the probability that all of its vertices are present.

Seen in this way, the probabilistic version PП of a (deterministic) combinatorial optimization problem П becomes another equally deterministic problem П′, the solutions of which have the same feasibility constraints as those of П but with a different objective function where vertex-probabilities intervene. In this sense, probabilistic combinatorial optimization is very close to what in the last couple of years has been called “one stage optimisation under independent decision models”, an area very popular in the stochastic optimization community.

What are the main mathematical problems dealing with probabilistic consideration of a problem П in the sense discussed above? We can identify at least five interesting mathematical and computational problems dealing with probabilistic combinatorial optimization:

1) write the functional down in an analytical closed form;

2) if such an expression of the functional is possible, prove that its value is polynomially computable (this amounts to proving that the modified problem П′ belongs to NP);

3) determine the complexity of the computation of the optimal a priori solution, i.e., of the solution optimizing the functional (in other words, determine the computational complexity of П′);

4) if П′ is NP-hard, study polynomial approximation issues;

5) always, under the hypothesis of the NP-hardness of П′, determine its complexity in the special cases where П is polynomial, and in the case of NP-hardness, study approximation issues.

Let us note that, although curious, point 2 in the above list in neither trivial nor senseless. Simply consider that the summation for the functional includes, in a graph of order n, 2n terms (one for each subgraph of G). So, polynomiality of the computation of the functional is, in general, not immediate.

Dealing with the contents of the book, in Chapter 1 probabilistic combinatorial optimization is formally introduced and some old relative results are quickly presented.

The rest of the book is subdivided into two parts. The first one (Part I) is more computational, while the second (Part II) is rather “structural”. In Part I, after formally introducing probabilistic combinatorial optimization and presenting some older results (Chapter 1), we deal with probabilistic versions of four paradigmatic combinatorial problems, namely, PROBABILISTIC MAX INDEPENDENT SET, PROBABILISTIC MIN VERTEX COVER, PROBABILISTIC LONGEST PATH and PROBABILISTIC MIN COLORING (Chapters 2, 3, 4 and 5, respectively). For any of them, we try, more or less, to solve the five types of problems just mentioned.

As the reader will see in what follows, even if, mainly in Chapters 2 and 3, several modification strategies are used and analyzed, the strategy that comes back for all the problems covered is the one consisting of moving absent vertices out of the a priori solution (it is denoted by MS for the rest of the book). Such a strategy is very quick, simple and intuitive but it does not always produce feasible solutions for any of the possible subgraphs (i.e., it is not always feasible). For instance, if it is feasible for PROBABILISTIC MAX INDEPENDENT SET, PROBABILISTIC MIN VERTEX COVER and PROBABILISTIC MIN COLORING, this is not the case for PROBABILISTIC LONGEST PATH, unless particular structure is assumed for the input graph. So, in Part II, we restrict ourselves to this particular strategy and assume that either MS is feasible, or, in case of unfeasibility, very little additional work is required in order to achieve feasible solutions. Then, for large classes of problems (e.g., problems where feasible solutions are subsets of the initial vertex-set or edge-set satisfying particular properties, such as stability, etc.), we investigate relations between these problems and their probabilistic counterparts (under MS). Such relations very frequently derive answers to the above mentioned five types of problems. Chapter 7 goes along the same lines as Chapter 6. We present a small compendium of probabilistic graph-problems (under MS). More precisely we revisit the most well-known and well-studied graph-problems and we investigate if strategy MS is feasible for any of them. For the problems for which this statement holds, we express the functional associated with it and, when possible, we characterize the optimal a priori solution and the complexity of its computation.

The book should be considered to be a monograph as in general it presents the work of its authors on probabilistic combinatorial optimization graph-problems. Nevertheless, we think that when the interested readers finish reading, they will be perfectly aware of the principles and the main issues of the whole subject area. Moreover, the book aims at being a self-contained work, requiring only some mathematical maturity and some knowledge about complexity and approximation theoretic notions. For help, some appendices have been added, dealing, on the one hand, with some mathematical preliminaries: on sets, relations and functions, on basic concepts from graph-theory and on some elements from discrete probabilities and, on the other hand, with elements of the complexity and the polynomial approximation theory: notorious complexity classes, reductions and NP-completeness and basics about the polynomial approximation of NP-hard problems. We hope that with all that, the reader will be able to read the book without much preliminary effort. Let us finally note that, for simplifying reading of the book, technical proofs are placed at the end of each chapter.

As we have mentioned in the beginning of this preface, we have worked in this domain since 1994. During all these years many colleagues have read, commented, improved and contributed to the topics of the book. In particular, we wish to thank Bruno Escoffier, Federico Della Croce and Christophe Picouleau for having working with, and encouraged us to write this book. The second author warmly thanks Elias Koutsoupias and Vassilis Zissimopoulos for frequent invitations to the University of Athens, allowing full-time work on the book, and for very fruitful discussions. Many thanks to Stratos Paschos for valuable help on LATEX.

Tender and grateful thanks to our families for generous and plentiful support and encouragement during the task.

Finally, it is always a pleasure to work with Chantal and Sami Menasce, Jon Lloyd and their colleagues at ISTE.

Cécile Murat and Vangelis Th. Paschos

Athens and Paris, October 2005

Chapter 1

A Short Insight into Probabilistic Combinatorial Optimization

1.1. Motivations and applications

The most common way in which probabilities are associated with combinatorial optimization problems is to consider that the data of the problem are deterministic (always present) and randomness carries over the relation between these data (for example, randomness on the existence of an edge linking two vertices in the framework of a random graph theory problem ([BOL 85]) or randomness on the fact that an element is included to a set or not, when dealing with optimization problems on set-systems or, even, randomness on the execution time of a task in scheduling problems). Then, in order to solve an optimization problem, algorithms (probabilistic or, more frequently, deterministic) are devised, and the mathematical expectation of the obtained solution is measured. A main characteristic of this approach is that probabilities do not intervene in the mathematical formulation of the problems but only in the mathematical analysis performed in order to get results.

More recently, in the late 1980s, another approach to the randomness of combinatorial optimization problems was developed: probabilities are associated with the data describing an optimization problem (for a particular datum, we can see the probability associated with it as a measure of how much this datum is likely to be present in the instance to be finally optimized) and, in this sense, probabilistic elements are explicitly included in the formulations of these problems. Such formulations give rise to what we will call probabilistic combinatorial optimization problems. Here, the objective function is a form of carefully defined mathematical expectation over all possible instances of size less than, or equal to, a given initial size.

The fact that, when dealing with probabilistic combinatorial problems, randomness lies in the presence of the data means that the underlying models are very suitable for the modelling of natural problems, where randomness is the quantification of uncertainty, or fuzzy information, or inability to forecast phenomena, etc.

For instance, in several versions of satellite shot planning problems, the uncertainty concerning meteorological conditions can be quantified by a system of probabilities. The optimization problems derived are, as we will see later in this chapter, clearly of probabilistic nature. If, on the other hand, during a salesman’s tour, some clients need not to be visited, he should omit them from his tour and if the fact that a client has to be visited or not is modelled in terms of probabilities-systems, then a probabilistic traveling salesman problem arises1. For similar or other reasons, starting from a transportation, or computer, or any other kind of network, we encounter problems like probabilistic shortest path problem2 or probabilistic longest path problem3, probabilistic minimum spanning tree problem4, etc. Also, in industrial automation, the systems for foreseeing workshops’ production give rise to probabilistic scheduling, or probabilistic set covering or probabilistic set packing, etc. Finally, in computer science, mainly when dealing with parallelism or distributed computation, probabilistic combinatorial optimization problems very frequently have to be solved. For instance, modeling load-balancing with non-uniform processors and failures possibility becomes a probabilistic graph partitioning problem; also in network reliability theory, many probabilistic routing problems are met ([BER 90b]).