Combinatorics, Algorithms, Probabilistic and Experimental Methodologies: First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers

Front Matter....Pages -
The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD ( I ) ≤ 11/9 OPT ( I ) + 6/9....Pages 1-11
Sequential Vector Packing....Pages 12-23
A Tighter Analysis of Set Cover Greedy Algorithm for Test Set....Pages 24-35
A More Effective Linear Kernelization for Cluster Editing....Pages 36-47
 CR-precis : A Deterministic Summary Structure for Update Data Streams....Pages 48-59
An Effective Refinement Algorithm Based on Swarm Intelligence for Graph Bipartitioning....Pages 60-69
On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems....Pages 70-81
A Digital Watermarking Scheme Based on Singular Value Decomposition....Pages 82-93
A New ( t , n ) −Threshold Scheme Based on Difference Equations....Pages 94-106
Clique-Transversal Sets in Cubic Graphs....Pages 107-115
On the L ( h , k )-Labeling of Co-comparability Graphs....Pages 116-127
An Approximation Algorithm for the General Mixed Packing and Covering Problem....Pages 128-139
Extending the Hardness of RNA Secondary Structure Comparison....Pages 140-151
On the On-Line Weighted k -Taxi Problem....Pages 152-162
Model Futility and Dynamic Boundaries with Application in Banking Default Risk Modeling....Pages 163-174
On the Minimum Risk-Sum Path Problem....Pages 175-185
Constrained Cycle Covers in Halin Graphs....Pages 186-197
Optimal Semi-online Algorithms for Scheduling with Machine Activation Cost....Pages 198-208
A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection....Pages 209-218
Online Coupon Consumption Problem....Pages 219-230
Application of Copula and Copula-CVaR in the Multivariate Portfolio Optimization....Pages 231-242
Online Capacitated Interval Coloring....Pages 243-254
Energy Efficient Heuristic Scheduling Algorithms for Multimedia Service....Pages 255-259
Call Control and Routing in SONET Rings....Pages 260-270
Fast Matching Method for DNA Sequences....Pages 271-281
All-Pairs Ancestor Problems in Weighted Dags....Pages 282-293
Streaming Algorithms for Data in Motion....Pages 294-304
A Scheduling Problem with One Producer and the Bargaining Counterpart with Two Producers....Pages 305-316
Phrase-Based Statistical Language Modeling from Bilingual Parallel Corpus....Pages 317-328
Optimal Commodity Distribution for a Vehicle with Fixed Capacity Under Vendor Managed Inventory....Pages 329-339
On-Line Bin Packing with Arbitrary Release Times....Pages 340-349
On the Complexity of the Max-Edge-Coloring Problem with Its Variants....Pages 350-361
Quantitative Analysis of Multi-hop Wireless Networks Using a Novel Paradigm....Pages 362-374
Inverse Min-Max Spanning Tree Problem Under the Weighted Sum-Type Hamming Distance....Pages 375-383
Robust Optimization Model for a Class of Uncertain Linear Programs....Pages 384-395
An Efficient Algorithm for Solving the Container Loading Problem....Pages 396-407
A Bijective Code for k -Trees with Linear Time Encoding and Decoding....Pages 408-420
Market-Based Service Selection Framework in Grid Computing....Pages 421-434
Informative Gene Selection and Tumor Classification by Null Space LDA for Microarray Data....Pages 435-446
Heuristic Search for 2D NMR Alignment to Support Metabolite Identification....Pages 447-458
A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array....Pages 459-470
Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem....Pages 471-482
Finding Pure Nash Equilibrium of Graphical Game Via Constraints Satisfaction Approach....Pages 483-494
A New Load Balanced Routing Algorithm for Torus Networks....Pages 495-503
Optimal Semi-online Scheduling Algorithms on a Small Number of Machines....Pages 504-515
Lower Bounds on Edge Searching....Pages 516-527
Back Matter....Pages -