Algorithmic Aspects in Information and Management: Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007, Proceedings (Lecture Notes in Computer Science, 4508)

This book constitutes the refereed proceedings of the Third International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, held in Portland, OR, USA in June 2007. The 39 revised full papers presented together with abstracts of three invited talks were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on graph algorithms, combinatorics, scheduling, graph theory, network algorithms, game theory, option theory, computational geometry, graph theory and combinatorics, as well as networks and data. Front Matter....Pages - Efficient Algorithms for k -Disjoint Paths Problems on DAGs....Pages 134-143 Acyclic Edge Colouring of Outerplanar Graphs....Pages 144-152 Smallest Bipartite Bridge-Connectivity Augmentation (Extended Abstract)....Pages 153-166 Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree....Pages 167-177 An Efficient Algorithm for the Evacuation Problem in a Certain Class of a Network with Uniform Path-Lengths....Pages 178-190 Online OVSF Code Assignment with Resource Augmentation....Pages 191-200 Optimal Joint Rate and Power Allocation in CDMA Networks....Pages 201-210 Suppressing Maximum Burst Size Throughout the Path with Non-work Conserving Schedulers....Pages 211-220 Solving Generalized Maximum Dispersion with Linear Programming....Pages 1-10 Significance-Driven Graph Clustering....Pages 11-26 An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs....Pages 27-36 Digraph Strong Searching: Monotonicity and Complexity....Pages 37-46 Algorithms for Counting 2- Sat Solutions and Colorings with Applications....Pages 47-57 Collaborative Ranking: An Aggregation Algorithm for Individuals’ Preference Estimation....Pages 58-67 A Compact Encoding of Rectangular Drawings with Efficient Query Supports....Pages 68-81 A New Efficient Algorithm for Computing the Longest Common Subsequence....Pages 82-90 Scheduling a Flexible Batching Machine....Pages 91-99 Global Search Method for Parallel Machine Scheduling....Pages 100-107 Releasing and Scheduling of Lots in a Wafer Fab....Pages 108-119 Mixed Criteria Packet Scheduling....Pages 120-133 Convex Hulls of Point-Sets and Non-uniform Hypergraphs....Pages 285-295 Optimal st -Orientations for Plane Triangulations....Pages 296-305 Minimum Spanning Tree with Neighborhoods....Pages 306-316 An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem....Pages 317-326 Optimal Field Splitting with Feathering in Intensity-Modulated Radiation Therapy....Pages 327-336 Approximating the Maximum Independent Set and Minimum Vertex Coloring on Box Graphs....Pages 337-345 BMA * : An Efficient Algorithm for the One-to-Some Shortest Path Problem on Road Maps....Pages 346-357 Strip Packing vs. Bin Packing....Pages 358-367 Probe Matrix Problems: Totally Balanced Matrices....Pages 368-377 Efficiency of Data Distribution in BitTorrent-Like Systems....Pages 378-388 Design of a Fuzzy PI Controller to Guarantee Proportional Delay Differentiation on Web Servers....Pages 389-398 Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots....Pages 399-410 A Heuristic Method for Selecting Support Features from Large Datasets....Pages 411-423 How to Play the Majority Game with Liars....Pages 221-230 On Satisfiability Games and the Power of Congestion Games....Pages 231-240 The Complexity of Algorithms Computing Game Trees on Random Assignments....Pages 241-250 An Efficient, and Fast Convergent Algorithm for Barrier Options....Pages 251-261 An Ingenious, Piecewise Linear Interpolation Algorithm for Pricing Arithmetic Average Options....Pages 262-272 Optimal Order Allocation with Discount Pricing....Pages 273-284 Game and Market Equilibria: Computation, Approximation, and Smoothed Analysis....Pages 424-424 Ad Auctions – Current and Future Research....Pages 425-425 Expressive Commerce and Its Application to Sourcing: How We Conducted $25 Billion of Generalized Combinatorial Auctions....Pages 426-426 Back Matter....Pages -

This book constitutes the refereed proceedings of the Third International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, held in Portland, OR, USA in June 2007.

The 39 revised full papers presented together with abstracts of 3 invited talks were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on graph algorithms, combinatorics, scheduling, graph theory, network algorithms, game theory, option theory, computational geometry, graph theory and combinatorics, as well as networks and data.

This book constitutes the refereed proceedings of the Third International Conference on Algorithmic Aspects in Information and Management, AAIM 2007, held in Portland, OR, USA in June 2007. The 39 revised full papers presented together with abstracts of 3 invited talks were carefully reviewed and selected from 120 submissions. The papers are organized in topical sections on graph algorithms, combinatorics, scheduling, graph theory, network algorithms, game theory, option theory, computational geometry, graph theory and combinatorics, as well as networks and data