The First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies was held in Hangzhou, China, in April 2007. The symposium provided an interdisciplinary forum for researchers to share their discoveries and approaches; search for ideas, methodologies, and tool boxes; find better, faster, and more accurate solutions; and develop a research agenda of common interest. This volume constitutes the refereed post-proceedings of the symposium.
Inside you’ll find 46 full papers. All the contributions were carefully reviewed to ensure that each one meets the highest standards of research and scholarship. Collectively, they represent some of the most important thinking and advancements in the field.
The papers address large data processing problems using different methodologies from major disciplines such as computer science, combinatorics, and statistics.
Author(s): György Dósa (auth.), Bo Chen, Mike Paterson, Guochuan Zhang (eds.)
Series: Lecture Notes in Computer Science 4614 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2007
Language: English
Pages: 530
Tags: Algorithm Analysis and Problem Complexity; Pattern Recognition; Simulation and Modeling; Data Mining and Knowledge Discovery; Computational Biology/Bioinformatics
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 -
