Approximation and Online Algorithms

Name: Approximation and Online Algorithms | 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers

Roberto Solis-Oba Giuseppe Persiano(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 26. März 2012

X, 278 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-29116-6 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title Page
Preface
Organization
Table of Contents
Approximation Algorithms for Schedulingand Packing Problems
Introduction
Scheduling with Fixed Jobs
Related Results
New Results
2D Strip Packing
Related Work
New Results
Multiple Knapsack Problem
Known Results
New Results
Scheduling on Uniform Processors
Known Results
New Results
References
Approximating Subset $k$ -Connectivity Problems
Introduction
Proof of Theorem 1
Proof of Theorem 2
Proof of Theorem 3
References
Learning in Stochastic Machine Scheduling
Introduction
Preliminaries and Scheduling Policies
Bayesian Methodology
Bayesian Scheduling Policies
Bounds on Scheduling Policies
Upper Bound on Performance Guarantees
Tightness of the Performance Guarantees
Lower Bound on the Performance Guarantee of SEPT
Lower Bound on the Performance Guarantee of -SEPT
Computational Results
Concluding Remarks
References
An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems
Introduction
Problem Statement
Our Algorithm
Decrease and Reset Algorithm (DRA)
How to Set the Coefficients for ``Optimality
Queueing Analysis
Analysis
Numerical Examples
Conclusions
References
Single Approximation for Biobjective Max TSP
Introduction
Preliminaries
Non Existence of a Single -Approximate Solution
A Generic Algorithm for Biobjective Max TSP
An Improved Analysis
Future Work
References
Parameterized Approximation Algorithms for Hitting Set
Introduction
A Simple Design for Parameterized Approximation
A Simple Branching for Approximation
A More Elaborated Analysis of a Factor-2 Approximation Algorithm for 3-HS
Approximating 3-HS with Degree Constraints
Further Questions
References
Approximation Algorithmsfor the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs
Introduction
Indegree-Based Algorithm
Expansion Algorithm
Expansion Algorithm for Undirected Graphs
Expansion Algorithm for Acyclic Digraphs
Performance Guarantee
Tight Example
MaxSNP-Hardness
Concluding Remarks
References
Optimization over Integers with Robustness in Cost and Few Constraints
Introduction
Uncertainty in the Objective
Uncertainty in Constraints
Applications
References
A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption
Introduction
Lower Bound
Conclusions
References
Scheduling Jobs on Identical and Uniform Processors Revisited
Introduction
Bounds for max-Gap(A) and the Running-Time
Scheduling on Uniform Processors
Algorithm for Case 3
References
Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat
Introduction
2-Stage Stochastic Graph Protection Problem in Trees
1-Stage Extension to Probabilistic Edge Transmission
References
Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models
Introduction
Formal Problem Definitions
Analyzing WLAPS for Homogeneous Processors
Restricting the Input Instance
A Lower Bound on WOpt
Potential Function Analysis
An O(1)-Competitive Algorithm for Two Functionality Types
Restricting the Input Instance
A Lower Bound of Opt
Potential Function Analysis
A Better Competitive Algorithm with $m_1 = m_ 2 = 1$
References
A New Perspective on List Update: Probabilistic Locality and Working Set
Introduction
List Update with Locality of Reference
Working Set Property for List Update
Experimental Results
Conclusions
References
OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm
Introduction
Randomized Selection Process
Preliminaries
Selection Process for OnlineMin
Probability Distribution of Ck
Algorithm OnlineMin
Algorithm
Algorithm Implementation
Data Structures
References
Faster and Simpler Approximation of Stable Matchings
Introduction
Algorithm
Description of Algorithm GS Modified
Correctness of Algorithm GS Modified
Extension to Stable b-Matchings
Data Structures and Running Time
Correctness of Algorithm ASBM
References
Simpler 3/4-Approximation Algorithms for MAX SAT
Introduction
Analysis with a Potential Function
Poloczek and Schnitger's Potential Function
A New Combinatorial Randomized Algorithm
A New Deterministic LP Rounding Algorithm
Conclusion and Future Directions
References
On Online Algorithms with Advice for the $k$ -Server Problem
Introduction
Preliminaries
An Upper Bound for General Metric Spaces
$k$ -Server with Advice on Trees
Non-lazy Optimum
The Algorithm
Special Metric Spaces and PATH-COVER
Conclusions
References
Improved Lower Bound for Online Strip Packing
Introduction
Sequence Construction
Lower Bound
Upper Bound
References
Competitive Router Scheduling with Structured Data
Introduction
Preliminaries
Models
Algorithm
Multiple Capacitated Links
Analysis of Algorithm PLink
A Lower Bound
The Effect of Many Links and Large Capacity
Extensions
Effective Redundancy
Multiple Service Levels
Instantaneous Network Model
References
Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems
Introduction
Preliminaries on Multi-objective Optimization and Approximation
Approximation with a Given Number of Solutions
Max Pos NAE
Max Partition
Max Matching
Approximation with One Solution
Max Bisection
Conclusion
References
Generalized Maximum Flows over Time
Introduction
Preliminaries
Complexity and Hardness of Approximation
Lossy Networks
Proportional Losses
A Variant of the Successive Shortest Path Algorithm
Turning the Algorithm into an FPTAS
Conclusion
References
The Price of Anarchy for Minsum Related Machine Scheduling
Introduction
Characterization of Optimal Solutions
Coordination Mechanism and Nash Equilibria
Upper Bound on the Price of Anarchy
Lower Bound on the Price of Anarchy
Concluding Remarks
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken