Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , , , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg : Imprint: Springer,
2009.
|
| Σειρά: | Lecture Notes in Computer Science,
5687 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- Contributed Talks of APPROX
- Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
- Adaptive Sampling for k-Means Clustering
- Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
- Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Truthful Mechanisms via Greedy Iterative Packing
- Resource Minimization Job Scheduling
- The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
- New Hardness Results for Diophantine Approximation
- PASS Approximation
- Optimal Sherali-Adams Gaps from Pairwise Independence
- An Approximation Scheme for Terrain Guarding
- Scheduling with Outliers
- Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- On the Optimality of Gluing over Scales
- On Hardness of Pricing Items for Single-Minded Bidders
- Real-Time Message Routing and Scheduling
- Approximating Some Network Design Problems with Node Costs
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- Minimizing Average Shortest Path Distances via Shortcut Edge Addition
- Approximating Node-Connectivity Augmentation Problems
- A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
- Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
- On the Complexity of the Asymmetric VPN Problem
- Contributed Talks of RANDOM
- Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Strong Parallel Repetition Theorem for Free Projection Games
- Random Low Degree Polynomials are Hard to Approximate
- Composition of Semi-LTCs by Two-Wise Tensor Products
- On the Security of Goldreich’s One-Way Function
- Random Tensors and Planted Cliques
- Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry
- Average-Case Analyses of Vickrey Costs
- A Hypergraph Dictatorship Test with Perfect Completeness
- Extractors Using Hardness Amplification
- How Well Do Random Walks Parallelize?
- An Analysis of Random-Walk Cuckoo Hashing
- Hierarchy Theorems for Property Testing
- Algorithmic Aspects of Property Testing in the Dense Graphs Model
- Succinct Representation of Codes with Applications to Testing
- Efficient Quantum Tensor Product Expanders and k-Designs
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Pseudorandom Generators and Typically-Correct Derandomization
- Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
- Tolerant Linearity Testing and Locally Testable Codes
- Pseudorandom Bit Generators That Fool Modular Sums
- The Glauber Dynamics for Colourings of Bounded Degree Trees
- Testing ±1-weight halfspace
- Small-Bias Spaces for Group Products
- Small Clique Detection and Approximate Nash Equilibria
- Testing Computability by Width Two OBDDs
- Improved Polynomial Identity Testing for Read-Once Formulas
- Smooth Analysis of the Condition Number and the Least Singular Value.
