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
- 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
- Organization of the part internal assignment
- Similarities and differences between the global and the local algorithm
- The complexity of internal assignment
- The global scenario (A kinetic data structure)
- The model
- The special radii
- Description of the global algorithm
- How the parts of the model interact
- Computation of the special radii
- The invariant
- Initialization
- The kinetic data structure
- Analysis of the global algorithm
- The local scenario
- Conclusion and open questions concerning internal assignment
- Bibliography