de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
Local, distributed approximation algorithms for geometric assignment problems / Sebastian Degener. 2010
Inhalt
Introduction
External assignment
Introduction to external assignment
Our contribution
Related work
Formal problem definition
Organization of the part external assignment
The complexity of external assignment
The heterogeneous scenario
Unearthing a single treasure
Unearthing a constant number of treasures
Unearthing a polynomial number of treasures
The homogeneous scenario
Variants of Unearth Treasures which are in P
Unearthing an arbitrary number of treasures
Unearthing a polynomial number of treasures
A local approximation algorithm with resource augmentation
Basic Definitions
A description of the algorithm
Clustering of robots and treasures: Correctness
Choosing clusters for a final solution: Correctness
Putting it all together
Generalizations
Conclusion and open questions concerning external assignment
Internal assignment
Introduction to internal assignment
Our contribution
Related work
Formal problem definition
The Mettu & Plaxton approach and radii
Radius associated with a point
Organization of the part internal assignment
Similarities and differences between the global and the local algorithm
The complexity of internal assignment
The locality
Exact facility location and the Mettu & Plaxton algorithm
The effect of dynamics
The global scenario (A kinetic data structure)
The model
Kinetic data structures
The special radii
Definition of the special radii
Cubes
Radius Associated with a Point
The ratio R
Walls around a Point and certificates
Description of the global algorithm
How the parts of the model interact
Computation of the special radii
The invariant
Initialization
The kinetic data structure
Event queue
Handling an update
Analysis of the global algorithm
The approximation factor of the global algorithm
Global maintenance of the invariant
Complexity
The local scenario
The model
The communication model
The round model
Modeling dynamics
How the parts of the model interact
Description of the local algorithm
The invariant
The algorithm
Events and initialization
Analysis of the algorithm
The approximation factor of the local algorithm
Main results about the local algorithm
Effects of events
The non-Euclidean case
Conclusion and open questions concerning internal assignment
Bibliography
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.