LEADER 05443nam 2200673Ia 450 001 9910840575603321 005 20230124183327.0 010 $a1-282-16499-6 010 $a9786612164996 010 $a0-470-61109-X 010 $a0-470-39367-X 035 $a(CKB)2550000000005906 035 $a(EBL)477695 035 $a(OCoLC)520990431 035 $a(SSID)ssj0000335966 035 $a(PQKBManifestationID)11241254 035 $a(PQKBTitleCode)TC0000335966 035 $a(PQKBWorkID)10277663 035 $a(PQKB)10758379 035 $a(MiAaPQ)EBC477695 035 $a(EXLCZ)992550000000005906 100 $a20070614d2008 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 00$aCombinatorial optimization and theoretical computer science$b[electronic resource] $einterfaces and perspectives : 30th anniversary of the LAMSADE /$fedited by Vangelis Th. Paschos 210 $aLondon $cISTE ;$aHoboken, NJ $cWiley$d2008 215 $a1 online resource (518 p.) 225 1 $aISTE ;$vv.24 300 $aDescription based upon print version of record. 311 $a1-84821-021-3 320 $aIncludes bibliographical references and index. 327 $aCombinatorial Optimization and Theoretical Computer Science; Contents; Preface; Chapter 1. The Complexity of Single Machine Scheduling Problems under Scenario-based Uncertainty; 1.1. Introduction; 1.2. Problem MinMax(1|prec|fmax, ? ); 1.2.1. Uncertainty on due dates; 1.2.2. Uncertainty on processing times and due dates; 1.3. Problem MinMax(1|| ? wj Cj, Wj ); 1.4. Problem MinMax(1|| ? Uj, ? ); 1.4.1. Uncertainty on due dates; 1.4.2. Uncertainty on processing times; 1.5. Bibliography; Chapter 2. Approximation of Multi-criteria Min and Max TSP(1, 2); 2.1. Introduction 327 $a2.1.1. The traveling salesman problem2.1.2. Multi-criteria optimization; 2.1.3. Organization of the chapter; 2.2. Overview; 2.3. The bicriteria TSP(1, 2); 2.3.1. Simple examples of the non-approximability; 2.3.2. A local search heuristic for the bicriteria TSP(1, 2); 2.3.3. A nearest neighbor heuristic for the bicriteria TSP(1, 2); 2.3.4. On the bicriteria Max TSP(1, 2); 2.4. k-criteria TSP(1, 2); 2.4.1. Non-approximability related to the number of generated solutions; 2.4.2. A nearest neighbor heuristic for the k-criteria TSP(1, 2); 2.5. Conclusion; 2.6. Bibliography 327 $aChapter 3. Online Models for Set-covering: The Flaw of Greediness3.1. Introduction; 3.2. Description of the main results and related work; 3.3. The price of ignorance; 3.4. Competitiveness of TAKE-ALL and TAKE-AT-RANDOM; 3.4.1. TAKE-ALL algorithm; 3.4.2. TAKE-AT-RANDOM algorithm; 3.5. The nasty flaw of greediness; 3.6. The power of look-ahead; 3.7. The maximum budget saving problem; 3.8. Discussion; 3.9. Bibliography; Chapter 4. Comparison of Expressiveness for Timed Automata and Time Petri Nets; 4.1. Introduction; 4.2. Time Petri nets and timed automata 327 $a4.2.1. Timed transition systems and equivalence relations4.2.2. Time Petri nets; 4.2.3. Timed automata; 4.2.4. Expressiveness and equivalence problems; 4.3. Comparison of semantics I, A and PA; 4.3.1. A first comparison between the different semantics of TPNs; 4.3.2. A second comparison for standard bounded TPN; 4.4. Strict ordering results; 4.5. Equivalence with respect to timed language acceptance; 4.5.1. Encoding atomic constraints; 4.5.2. Resetting clocks; 4.5.3. The complete construction; 4.5.4. ? (A) and A accept the same timed language; 4.5.5. Consequences of the previous results 327 $a4.6. Bisimulation of TA by TPNs4.6.1. Regions of a timed automaton; 4.6.2. From bisimulation to uniform bisimulation; 4.6.3. A characterization of bisimilarity; 4.6.4. Proof of necessity; 4.6.5. First construction; 4.6.6. Second construction; 4.6.7. Complexity results; 4.7. Conclusion; 4.8. Bibliography; Chapter 5. A "Maximum Node Clustering" Problem; 5.1. Introduction; 5.2. Approximation algorithm for the general problem; 5.3. The tree case; 5.3.1. Dynamic programming; 5.3.2. A fully polynomial time approximation scheme; 5.4. Exponential algorithms for special cases; 5.5. Bibliography 327 $aChapter 6. The Patrolling Problem: Theoretical and Experimental Results 330 $aThis volume is dedicated to the theme "Combinatorial Optimization - Theoretical Computer Science: Interfaces and Perspectives" and has two main objectives: the first is to show that bringing together operational research and theoretical computer science can yield useful results for a range of applications, while the second is to demonstrate the quality and range of research conducted by the LAMSADE in these areas. 410 0$aISTE 606 $aCombinatorial optimization$xComputer programs 606 $aComputer science$xMathematics 615 0$aCombinatorial optimization$xComputer programs. 615 0$aComputer science$xMathematics. 676 $a519.6/4 676 $a519.64 686 $aSK 890$2rvk 686 $aST 130$2rvk 701 $aPaschos$b Vangelis Th$0944252 712 02$aLaboratoire d'analyse et mode?lisation de syste?mes pour l'aide a? la de?cision (France) 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910840575603321 996 $aCombinatorial optimization and theoretical computer science$94136448 997 $aUNINA