Probabilistic Combinatorial Optimization on Graphs

This book deals with probabilistic combinatorial optimization. It discusses 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 colouring. The main working hypothesis adopted is called a priori optimization. Starting from a priori solution of a 'super-instance' of a problem, where any datum is present with a certain probability, a priori optimization consists of modifying in order to fit the real instance to be optimized, that is, a sub-instance of the initial super-instance. The main objective is to determine a solution of the initial instance, called the a priori solution, so that its restriction to the effective instance is optimized (for some predefined criterion such as optimality, approximation within a certain level, etc.). This is a comprehensive survey requiring only some mathematical understanding ...