Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques : 4th International Workshop on Approximation Algorithms for ... Workshop on Randomization and Approx - Softcover

9783662187197: Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques : 4th International Workshop on Approximation Algorithms for ... Workshop on Randomization and Approx

Softcover

ISBN 10: 3662187191 ISBN 13: 9783662187197

Publisher: Springer, 2014

Invited Talks.- Using Complex Semidefinite Programming for Approximating MAX E2-LIN3.- Hill-Climbing vs. Simulated Annealing for Planted Bisection Problems.- Web Search via Hub Synthesis.- Error-Correcting Codes and Pseudorandom Projections.- Order in Pseudorandomness.- Contributed Talks of APPROX.- Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows.- On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique.- Online Weighted Flow Time and Deadline Scheduling.- An Online Algorithm for the Postman Problem with a Small Penalty.- A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem.- Approximation Schemes for Ordered Vector Packing Problems.- Incremental Codes.- A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set.- Approximation Algorithms for Budget-Constrained Auctions.- Minimizing Average Completion of Dedicated Tasks and Interval Graphs.- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting.- 0.863-Approximation Algorithm for MAX DICUT.- The Maximum Acyclic Subgraph Problem and Degree-3 Graphs.- Some Approximation Results for the Maximum Agreement Forest Problem.- Contributed Talks of RANDOM.- Near-optimum Universal Graphs for Graphs with Bounded Degrees.- On a Generalized Ruin Problem.- On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation.- Exact Sampling in Machine Scheduling Problems.- On Computing Ad-hoc Selective Families.- L Infinity Embeddings.- On Euclidean Embeddings and Bandwidth Minimization.- The Non-approximability of Non-Boolean Predicates.- On the Derandomization of Constant Depth Circuits.- Testing Parenthesis Languages.- Proclaiming Dictators and Juntas or Testing Boolean Formulae.- Equitable Coloring Extends Chernoff-Hoeffding Bounds.

"synopsis" may belong to another edition of this title.