Algorithmic Aspects in Information and Management: 5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009, Proceedings (Lecture Notes in Computer Science (5564))

This book constitutes the proceedings of the 5th International Conference on Algorithmic Aspects in Information Management, AAIM 2009, held in San Francisco, CA, USA, in June 2009. The 25 papers presented together with the abstracts of two invited talks were carefully reviewed and selected for inclusion in this book. While the areas of information management and management science are full of algorithmic challenges, the proliferation of data (Internet, biology, finance etc) has called for the design of efficient and scalable algorithms and data structures for their management and processing. This conference is intended for original algorithmic research on immediate applications and/or fundamental problems pertinent to information management and management science, broadly construed. The conference aims at bringing together researchers in Computer Science, Operations Research, Economics, Game Theory, and related disciplines. Front Matter....Pages - Algorithmic Challenge in Online Advertising....Pages 1-1 Parallel Algorithms for Collaborative Filtering....Pages 2-2 On the Approximability of Some Haplotyping Problems....Pages 3-14 On Acyclicity of Games with Cycles....Pages 15-28 Discrete online TSP....Pages 29-42 On Approximating an Implicit Cover Problem in Biology....Pages 43-54 Power Indices in Spanning Connectivity Games....Pages 55-67 Efficiently Generating k -Best Solutions to Procurement Auctions....Pages 68-84 Integer Polyhedra for Program Analysis....Pages 85-99 Line Segment Facility Location in Weighted Subdivisions....Pages 100-113 Algorithms for Placing Monitors in a Flow Network....Pages 114-128 Three Results on Frequency Assignment in Linear Cellular Networks....Pages 129-139 Link Distance and Shortest Path Problems in the Plane....Pages 140-151 Orca Reduction and ContrAction Graph Clustering....Pages 152-165 Equiseparability on Terminal Wiener Index....Pages 166-174 Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges....Pages 175-187 Optimal Auctions Capturing Constraints in Sponsored Search....Pages 188-201 A Note on Estimating Hybrid Frequency Moment of Data Streams....Pages 202-211 Two-Level Push-Relabel Algorithm for the Maximum Flow Problem....Pages 212-225 A More Relaxed Model for Graph-Based Data Clustering: s -Plex Editing....Pages 226-239 Dynamic Position Auctions with Consumer Search....Pages 240-250 Nonlinear Optimization over a Weighted Independence System....Pages 251-264 Improved Online Algorithms for Multiplexing Weighted Packets in Bounded Buffers....Pages 265-278 Latency Constrained Aggregation in Chain Networks Admits a PTAS....Pages 279-291 Cutting a Cake for Five People....Pages 292-300 PLDA: Parallel Latent Dirichlet Allocation for Large-Scale Applications....Pages 301-314 On Job Scheduling with Preemption Penalties....Pages 315-325 Back Matter....Pages -

This book constitutes the proceedings of the 5th International Conference on Algorithmic Aspects in Information Management, AAIM 2009, held in San Francisco, CA, USA, in June 2009.

The 25 papers presented together with the abstracts of two invited talks were carefully reviewed and selected for inclusion in this book.

While the areas of information management and management science are full of algorithmic challenges, the proliferation of data (Internet, biology, finance etc) has called for the design of efficient and scalable algorithms and data structures for their management and processing. This conference is intended for original algorithmic research on immediate applications and/or fundamental problems pertinent to information management and management science, broadly construed. The conference aims at bringing together researchers in Computer Science, Operations Research, Economics, Game Theory, and related disciplines.