| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNINA9910139491403321 |
|
|
Titolo |
Combinatorial optimization and theoretical computer science [[electronic resource] ] : interfaces and perspectives : 30th anniversary of the LAMSADE / / edited by Vangelis Th. Paschos |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
London, : ISTE |
|
Hoboken, NJ, : Wiley, 2008 |
|
|
|
|
|
|
|
|
|
ISBN |
|
1-282-16499-6 |
9786612164996 |
0-470-61109-X |
0-470-39367-X |
|
|
|
|
|
|
|
|
Descrizione fisica |
|
1 online resource (518 p.) |
|
|
|
|
|
|
Collana |
|
|
|
|
|
|
Classificazione |
|
|
|
|
|
|
|
|
Altri autori (Persone) |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
|
|
Soggetti |
|
Combinatorial optimization - Computer programs |
Computer science - Mathematics |
Electronic books. |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
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. |
|
|
|
|
|
|
|
| |