Algorithmic Aspects in Information and Management: 6th International Conference, AAIM 2010, Weihai, China, July 19-21, 2010. ProceedingsBo Chen While the areas of information management and management science are full of algorithmic challenges, the proliferation of data has called for the design of e?cient and e?ective algorithms and data structures for their management and processing. The International Conference on Algorithmic Aspects in Information and Management(AAIM) is intended for originalalgorithmicresearchon immediate applications and/or fundamental problems pertinent to information mana- ment and management science to be broadly construed. The conference aims at bringing together researchers in computer science, operations research, applied mathematics, economics, and related disciplines. This volume contains papers presented at AAIM 2010: the 6th International Conference on Algorithmic Aspects in Information and Management, which was held during July 19-21, 2010, in Weihai, China. We received a total of 50 s- missions.Eachsubmissionwasreviewedbythreemembersof the ProgramC- mittee or their deputies on the quality, originality, soundness, and signi?cance of its contribution. The committee decided to accept 31 papers. The program also included two invited keynote talks. The success of the conference resulted from the input of many people. We would like ?rst of all to thank all the members of the Program Committee for their expert evaluation of the submissions. The local organizers in the School of Computer Science and Technology, Shandong University, did an extraordinary job, for which we are very grateful. We thank the National Natural Science Foundation of China, Montana State University (USA), University of Warwick (UK), and Shandong University (China) for their sponsorship. |
Contents
Comparison of Two Algorithms for Computing Page Importance | 1 |
The Invisible Hand for Risk Averse Investment in Electricity Generation | 12 |
Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data | 13 |
The K kCapacitated Spanning Tree Problem | 25 |
Optimal Algorithms for the Economic LotSizing Problem with Multisupplier | 35 |
Synthetic Road Networks | 46 |
Computing Exact and Approximate Nash Equilibria in 2Player Games | 58 |
Where Would Refinancing Preferences Go? | 70 |
Indexing Similar DNA Sequences | 180 |
Online Scheduling on Two Uniform Machines to Minimize the Makespan with a Periodic Availability Constraint | 191 |
A New Smoothing Newton Method for Symmetric Cone Complementarity Problems | 199 |
Approximation Algorithms for Scheduling with a Variable Machine Maintenance | 209 |
Bounded ParallelBatch Scheduling on Unrelated Parallel Machines | 220 |
Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles | 229 |
Randomized Approaches for Nearest Neighbor Search in Metric Space When Computing the Pairwise Distance Is Extremely Expensive | 243 |
A PrimalDual Approximation Algorithm for the kLevel Stochastic Facility Location Problem | 253 |
Approximating Maximum Edge 2Coloring in Simple Graphs | 78 |
A Linear Kernel for CoPathCycle Packing | 90 |
A VaR Algorithm for Warrants Portfolio | 103 |
Some Results on Incremental Vertex Cover Problem | 112 |
Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction | 119 |
Point Location in the ContinuousTime Moving Network | 131 |
Coordinated Scheduling of Production and Delivery with Production Window and Delivery Capacity Constraints | 141 |
Inverse 1median Problem on Trees under Weighted l_ Norm | 150 |
On the Approximability of the Vertex Cover and Related Problems | 161 |
Feasibility Testing for DialaRide Problems | 170 |
Optimal Semionline Scheduling Algorithms on Two Parallel Identical Machines under a Grade of Service Provision | 261 |
Varieties of Regularities in Weighted Sequences | 271 |
Online Uniformly Inserting Points on Grid | 281 |
Kernelization for Cycle Transversal Problems | 293 |
Online Splitting Interval Scheduling on m Identical Machines | 304 |
Extended Tabu Search on Fuzzy Traveling Salesman Problem in Multicriteria Analysis | 314 |
Efficient Exact and Approximate Algorithms for the Complement of Maximal Strip Recovery | 325 |
Author Index | 334 |
Other editions - View all
Algorithmic Aspects in Information and Management: 6th International ... Bo Chen Limited preview - 2010 |
Common terms and phrases
4-cycle analysis applied approximation algorithm arrive assigned assume bound called China competitive ratio completion compute connected consider constraint construct contains corresponding cost cycle defined deleted delivery denote different distance distribution edge example exists feasible find first function give given graph grid Heidelberg Hence increase insertion instance interval iteration least Lemma length linear lower bound machine maximal method minimize Nash neighbors nodes Note objects obtain Operations optimal solution otherwise packing path performance period phase points polynomial position possible present problem production Proof properties proposed prove reduction Research respectively risk schedule Science segments selected sequence similar single solution solve space square Step structure suffix Suppose Theorem tour tree University vertex cover vertices weighted window