Algorithmic Aspects in Information and Management

Thepapersinthis volumewerepresentedatthe5thInternationalConferenceon Algorithmic Aspects in Information and Management (AAIM 2009), held June 15-17, 2009, in San Francisco, California. The topics cover mostly algorithmic applications in information management and management science. A total of 41 papers were submitted to the conference.After an on-line paper review process, the Program Committee accepted 25 papers to be presented. The international Program Committee included Tetsuo Asano, Marshall Bern, Daniel Bienstock, Danny Z. Chen, Camil Demetrescu, Lisa Fleischer, Rudolf Fleischer, Martin Frer, Andrew Goldberg, Mordecai Golin, Monika Henzinger, Seok-Hee Hong, Ming-Yang Kao, Xiang-Yang Li, Mohammad Mahdian, Tom McCormick, Junfeng Pan, Rong Pan, Panos Pardalos, Tomasz Radzik, Rajeev Raman, Martin Scholz, Robert Schreiber, Dou Shen, Xiaodong Wu, Jinhui Xu, QiangYang,HuamingZhang,YunhongZhouandBinhaiZhu.Itisexpectedthat many of the accepted papers will appear in a more complete form in scienti?c journals. The submitted papers are from Algeria, Argentina, Australia, Chile, China, Czech Republic, Denmark, France, Germany, Hong Kong, India, Iran, Israel, Japan, Taiwan, UK and USA. Each paper was evaluated by at least three P- gram Committee members (four is also common), assisted in some cases by subreferees (listed in the proceedings). In addition to selected papers, the c- ference also included two invited presentations by Andrei Broder and Edward Chang. We thank allthe people who made this meeting possible:the authorsfor s- mitting papers, the Program Committee members for their excellent work, and the two invited speakers. Finally, we thank the Organizing Committee members whose hard work make this conference possible.

Inhalt

Algorithmic Challenge in Online Advertising.- Parallel Algorithms for Collaborative Filtering.- On the Approximability of Some Haplotyping Problems.- On Acyclicity of Games with Cycles.- Discrete online TSP.- On Approximating an Implicit Cover Problem in Biology.- Power Indices in Spanning Connectivity Games.- Efficiently Generating k-Best Solutions to Procurement Auctions.- Integer Polyhedra for Program Analysis.- Line Segment Facility Location in Weighted Subdivisions.- Algorithms for Placing Monitors in a Flow Network.- Three Results on Frequency Assignment in Linear Cellular Networks.- Link Distance and Shortest Path Problems in the Plane.- Orca Reduction and ContrAction Graph Clustering.- Equiseparability on Terminal Wiener Index.- Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges.- Optimal Auctions Capturing Constraints in Sponsored Search.- A Note on Estimating Hybrid Frequency Moment of Data Streams.- Two-Level Push-Relabel Algorithm for the Maximum Flow Problem.- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Editing.- Dynamic Position Auctions with Consumer Search.- Nonlinear Optimization over a Weighted Independence System.- Improved Online Algorithms for Multiplexing Weighted Packets in Bounded Buffers.- Latency Constrained Aggregation in Chain Networks Admits a PTAS.- Cutting a Cake for Five People.- PLDA: Parallel Latent Dirichlet Allocation for Large-Scale Applications.- On Job Scheduling with Preemption Penalties.