This book constitutes the refereed proceedings of the 4th International Frontiers of Algorithmics Workshop, FAW 2010, held in Wuhan, China, in August 2010. The 28 revised full papers presented together with the abstracts of 3 invited talks were carefully reviewed and selected from 57 submissions. The Workshop will provide a focused forum on current trends of research on algorithms, discrete structures, and their applications, and will bring together international experts at the research frontiers in these areas to exchange ideas and to present significant new results. The mission of the Workshop is to stimulate the various fields for which algorithmics can become a crucial enabler, and to strengthen the ties between the Eastern and Western research communities of algorithmics and applications.
Author(s): Kurt Mehlhorn, Pascal Schweitzer (auth.), Der-Tsai Lee, Danny Z. Chen, Shi Ying (eds.)
Series: Lecture Notes in Computer Science 6213 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 339
Tags: Algorithm Analysis and Problem Complexity; Software Engineering; Discrete Mathematics in Computer Science; Logics and Meanings of Programs; Mathematics of Computing; Theory of Computation
Front Matter....Pages -
Progress on Certifying Algorithms....Pages 1-5
Computational Geometry for Uncertain Data....Pages 6-6
On Foundations of Services Interoperation in Cloud Computing....Pages 7-10
Mechanism Design for Multi-slot Ads Auction in Sponsored Search Markets....Pages 11-22
Truthful Auction for CPU Time Slots....Pages 23-34
Top- d Rank Aggregation in Web Meta-search Engine....Pages 35-44
Minimum Common String Partition Revisited....Pages 45-52
Inapproximability of Maximal Strip Recovery: II....Pages 53-64
Minimizing Total Variation for Field Splitting with Feathering in Intensity-Modulated Radiation Therapy....Pages 65-76
Approximation Schemes for Scheduling with Availability Constraints....Pages 77-88
An $\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ Space Lower Bound for Finding ε -Approximate Quantiles in a Data Stream....Pages 89-100
Improved Sublinear Time Algorithm for Width-Bounded Separators....Pages 101-112
Constant Time Generation of Biconnected Rooted Plane Graphs....Pages 113-123
Solving General Lattice Puzzles....Pages 124-135
A Hybrid Graph Representation for Recursive Backtracking Algorithms....Pages 136-147
On Tractable Exponential Sums....Pages 148-159
Recognizing d -Interval Graphs and d -Track Interval Graphs....Pages 160-171
Categorial Semantics of a Solution to Distributed Dining Philosophers Problem....Pages 172-184
Approximation Algorithms for the Capacitated Domination Problem....Pages 185-196
A Polynomial Time Approximation Scheme for Embedding Hypergraph in a Weighted Cycle....Pages 197-209
FPTAS’s for Some Cut Problems in Weighted Trees....Pages 210-221
Deterministic Online Call Control in Cellular Networks and Triangle-Free Cellular Networks....Pages 222-233
Online Algorithms for the Newsvendor Problem with and without Censored Demands....Pages 234-249
O ((log n ) 2 ) Time Online Approximation Schemes for Bin Packing and Subset Sum Problems....Pages 250-261
Path Separability of Graphs....Pages 262-273
Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings....Pages 274-284
Computing Minimum Diameter Color-Spanning Sets....Pages 285-292
Approximation Algorithm for the Largest Area Convex Hull of Same Size Non-overlapping Axis-Aligned Squares....Pages 293-303
Optimum Sweeps of Simple Polygons with Two Guards....Pages 304-315
Adaptive Algorithms for Planar Convex Hull Problems....Pages 316-326
New Algorithms for Barrier Coverage with Mobile Sensors....Pages 327-338
Back Matter....Pages -
