Combinatorial optimization and theoretical computer science [[electronic resource] ] : interfaces and perspectives : 30th anniversary of the LAMSADE / / edited by Vangelis Th. Paschos

• Pubblicazione: London, : ISTE; Hoboken, NJ, : Wiley, 2008
• Descrizione fisica: 1 online resource (518 p.)
• Disciplina: 519.6/4; 519.64
• Soggetto topico: Combinatorial optimization - Computer programs; Computer science - Mathematics
• Soggetto genere / forma: Electronic books.
• Classificazione: SK 890; ST 130
• Altri autori: PaschosVangelis Th
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: Combinatorial 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 ; 2.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 ; Chapter 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 ; 4.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 ; 4.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 ; Chapter 6. The Patrolling Problem: Theoretical and Experimental Results
• Sommario/riassunto: This 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.
• Titolo autorizzato: Combinatorial optimization and theoretical computer science
• ISBN: 1-282-16499-6; 9786612164996; 0-470-61109-X; 0-470-39367-X
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910139491403321
• Lo trovi qui: Univ. Federico II
• Serie: ISTE