Probabilistic Combinatorial Optimization on Graphs

Cécile Murat, Vangelis Th. Paschos

• Publisher: Wiley-ISTE
• Year: 2013
• Print ISBN: 9781905209330
• eBook ISBN: 9781118614136
• Edition: 1
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

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.

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 arises¹. For similar or other reasons, starting from a transportation, or computer, or any other kind of network, we encounter problems like probabilistic shortest path problem² or probabilistic longest path problem³, probabilistic minimum spanning tree problem⁴, 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]).

In all, models of probabilistic nature are very suitable and appropriate real-life problems where randomness is a constant source of concern and, on the other hand, the study of the problems derived from these models are very attractive as mathematical abstraction of real systems. Another reason motivating work on probabilistic combinatorial optimization is the study and the analysis of the stability of the optimal solutions of deterministic combinatorial optimization problems when the considered instances are perturbed. For problems defined on graphs, more particularly, these perturbations are simulated by the occurrence, or the absence, of subsets of vertices (see, for example, [PEE 99] where probabilistic combinatorial optimization approaches and concepts are used to yield robust solutions for an on-line traffic-assignment problem).

Informally, given a combinatorial optimization graph⁵-problem Π, defined on a graph G(V, E), an instance of its probabilistic counterpart, denoted by PΠ, is built by associating a probability p_i with any vertex v_i in V. This probability is considered as the presence-probability of v_i in the subgraph of G on which Π will be finally solved. Problem PΠ expresses the fact that Π will, eventually, have to be solved not on the whole G, but rather on some of its subgraphs that will be specified very shortly before the solution in this subgraph is required.

In order to illustrate the issue outlined...

Table of contents

• Cover
• Title Page
• Copyright
• Preface
• Chapter 1: A Short Insight into Probabilistic Combinatorial Optimization
• FIRST PART: Probabilistic Graph-problems
• SECOND PART: Structural Results
• Appendix A: Mathematical Preliminaries
• Appendix B: Elements of the Complexity and the Approximation Theory
• Bibliography
• Index