PROBABILISTIC COMBINATORIAL OPTIMIZATION ON GRAPHS
THE FACT THAT, WHEN DEALING WITH PROBABILISTIC COMBINATORIAL PROBLEMS, RANDOM- NESS LIES IN THE PRESENCE OF THE DATA MEANS THAT THE UNDERLYING MODELS ARE VERY SUIT- ABLE FOR THE MODELLING OF NATURAL PROBLEMS, WHERE RANDOMNESS IS THE QUANTI?CATION 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 QUANTI?ED 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 PROBA- BILISTIC 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, PROB- ABILISTIC 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, PROBABILIS- TIC COMBINATORIAL OPTIMIZATION PROBLEMS VERY FREQUENTLY HAVE TO BE SOLVED FOR IN- STANCE, MODELING LOAD-BALANCING WITH NON-UNIFORM PROCESSORS AND FAILURES POSSIBILITY 1 GIVEN A COMPLETE GRAPH ON N VERTICES, DENOTED BY KN, WITH POSITIVE DISTANCES ON ITS EDGES, THE MINIMUM TRAVELING SALESMAN PROBLEM CONSISTS OF MINIMIZING THE COST OF A HAMILTONIAN CYCLE (SEE SECTION A 2 IN APPENDIX A), THE COST OF SUCH A CYCLE BEING THE SUM OF THE DISTANCES OF ITS EDGES 2 GIVEN AN EDGE-WEIGHTED DIRECTED OR UNDIRECTED GRAPH G(V, E, ?W) AND EITHER A ?XED VERTEX S (?RST VERSION), OR TWO ?XED VERTICES S AND T (SECOND VERSION), THE OBJECTIVE FOR THE ?RST VERSION IS TO DETERMINE MINIMUM-WEIGHT PATHS FROM S TO ANY OTHER VERTEX OF G; FOR THE SECOND VERSION, THE OBJECTIVE IS TO DETERMINE A MINIMUM-WEIGHT PATH FROM S TO T, THE WEIGHT OF A PATH BEING THE SUM OF THE WEIGHTS OF ITS EDGES; THE MOST FAMOUS VARIANTS OF THESE VERSIONS ARE THE ONES WHERE G IS ASSUMED DIRECTED; IN THIS CASE, THE THREE MOST-KNOWN POLYNOMIAL ALGORITHMS SOLVING THE ?RST VERSION OF THE PROBLEM ARE THE ONES OF DIJKSTRA ([DIJ 59]), UNDER THE ASSUMPTION THAT EDGE-WEIGHTS ARE NON-NEGATIVE, AND OF BELLMAN ([BEL 57]), UNDER THE ASSUMPTION THAT THE INPUT- GRAPH CONTAINS NO CIRCUIT; NO ALGORITHM IS KNOWN FOR THE SECOND VERSION OF THE PROBLEM THAT IS SOLVED AS A SPECIAL CASE OF THE ?RST VERSION; A THIRD VERSION OF THE SHORTEST PATH PROBLEM, WHERE WE SEARCH FOR SHORTEST PATHS FOR ANY PAIR OF VERTICES, IS POLYNOMIALLY SOLVED BY THE ALGORITHM OF FLOYD ([FLO 62]) 3 GIVEN A GRAPH G(V, E), AN EDGE-WEIGHT FUNCTION W : E ?Q, AND TWO SPECI?C VERTICES S AND T, THE LONGEST PATH PROBLEM CONSISTS OF DETERMINING A MAXIMUM TOTAL-WEIGHT SIMPLE PATH FROM S TO T, THE TOTAL WEIGHT OF A PATH BEING THE SUM OF THE WEIGHTS OF ITS EDGES 4 GIVEN AN EDGE-WEIGHTED UNDIRECTED GRAPH G(V, E, ?W), THE OBJECTIVE IS TO DETERMINE A MINIMUM-WEIGHT TREE SPANNING V , THE WEIGHT OF SUCH A TREE BEING THE SUM OF THE WEIGHTS OF ITS EDGES; THE MOST FAMOUS POLYNOMIAL ALGORITHM SOLVING THIS PROBLEM IS THE ONE OF KRUSKAL ([KRU 56]) PROBABILISTIC COMBINATORIAL OPTIMIZATION ON GRAPHS