This book constitutes the refereed proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, AAIM 2008, held in Shanghai, China, in June 2008. The 30 revised full papers presented together with abstracts of 2 invited talks were carefully reviewed and selected from 53 submissions. The papers cover original algorithmic research on immediate applications and/or fundamental problems pertinent to information management and management science. Topics addressed are: approximation algorithms, geometric data management, biological data management, graph algorithms, computational finance, mechanism design, computational game theory, network optimization, data structures, operations research, discrete optimization, online algorithms, FPT algorithms, and scheduling algorithms.
Erscheinungsdatum: 03.06.2008

lgli/Cs_Computer science/CsLn_Lecture notes/A/Algorithmic Aspects in Information and Management, 4 conf., AAIM 2008(LNCS5034, Springer, 2008)(ISBN 9783540688655)(359s)_CsLn_.pdf

lgrsnf/Cs_Computer science/CsLn_Lecture notes/A/Algorithmic Aspects in Information and Management, 4 conf., AAIM 2008(LNCS5034, Springer, 2008)(ISBN 9783540688655)(359s)_CsLn_.pdf

nexusstc/Algorithmic Aspects in Information and Management/0e50efc5549aac7aceffe4935fc6c34a.pdf

scihub/10.1007/978-3-540-68880-8.pdf

zlib/Education Studies & Teaching/International Conferences and Symposiums/Ding-Zhu Du (auth.), Rudolf Fleischer, Jinhui Xu (eds.)/Algorithmic Aspects in Information and Management: 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings_654011.pdf

[edited by] Rudolf Fleischer, Jinhui Xu

AAIM 2005 (2008 Shanghai, China)

pdfsam-console (Ver. 1.1.5e)

Fleischer, Rudolf

AAIM (Conference)

Springer Berlin Heidelberg : Imprint: Springer

Springer Spektrum. in Springer-Verlag GmbH

Steinkopff. in Springer-Verlag GmbH

Springer-Verlag New York Inc

Springer London, Limited

Springer Nature

Lecture notes in computer science -- 5034, 1st ed., New York, New York State, 2008

Lecture notes in computer science, 5034, Berlin ; New York, ©2008

Lecture notes in computer science, 5034, Berlin, Heidelberg, 2008

LNCS sublibrary, 5034, 1st ed, Berlin, Heidelberg, 2008

Germany, Germany

1, 20080617

2013

Kolxo3 -- 0

lg226329

producers:
iText 2.0.7 (by lowagie.com)

{"container_title":"Lecture Notes in Computer Science","edition":"1","isbns":["354068865X","3540688803","9783540688655","9783540688808"],"issns":["0302-9743","1611-3349"],"last_page":352,"publisher":"Springer","series":"Lecture Notes in Computer Science 5034 : Information Systems and Applications, incl. Internet/Web, and HCI"}

Includes bibliographical references and index.

Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs 10
Nash Bargaining Via Flexible Budget Markets 11
On the Minimum Hitting Set of Bundles Problem 12
Introduction 12
Applications of the mhsb Problem 13
Contribution 14
Organization of the Paper 14
Inapproximability 14
Approximation Algorithms 15
Greedy Algorithms 15
LP-Based Algorithms 15
Derandomization 20
Integrality Gap 21
About MIN $k$-SAT 22
Concluding Remarks 22
Speed Scaling with a Solar Cell 24
Introduction 24
Related Results 25
Our Results 25
Formal Problem Statement 26
Preliminaries 27
Convex Programming Formulation 28
Recognizing an Optimal Schedule 29
Performance of YDS 32
An Online Algorithm 34
Engineering Label-Constrained Shortest-Path Algorithms 36
Introduction 36
Related Work 37
Foundation 37
Problem Statement 37
Applications 38
Algorithms 38
Product Network 38
Speed-Up Techniques 39
Experimental Study 40
Setup 40
Multimodal Routing 41
k-Similar Paths 44
Conclusion 45
New Upper Bounds on Continuous Tree Edge-Partition Problem 47
Introduction 47
Spine Decomposition of T 48
The Max-Min Continuous Edge-Partition Problem 49
Computing q(v), vV(T){rT} 49
Main Idea and the Overall Approach 50
Computing Edge-Partitions at all jth-Level Spines, 1j 50
The Min-Max Continuous Edge-Partition Problem 56
An Algorithm for the Ratio Search Problem 56
Summary 58
A Meeting Scheduling Problem Respecting Time and Space 59
Introduction 59
Problem Definition 60
Geometric Interpretation of the Problem 61
The LP-Approach 62
General Framework of LP-Type Problems 62
Preparations for Applying the General Framework 63
Application of the General Framework 65
Summary and Current Work 68
Fixed-Parameter Algorithms for Kemeny Scores 69
Introduction 69
Preliminaries 71
Parameterization by the Kemeny Score 72
Problem Kernel 72
Search Tree Algorithm 73
Parameterization by the Maximum KT-Distance 74
Parameterization by the Number of Candidates 77
Ties and Incomplete Votes 77
Kemeny Score with Ties 78
Incomplete Votes 79
The Distributed Wireless Gathering Problem 81
Introduction 81
Preliminaries 85
A lower Bound for Distributed Algorithms 85
A Distributed Algorithm and Its Analysis 87
The Algorithm 87
The Analysis 88
An Extension 90
Conclusion and Open Problems 91
Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement 93
Introduction 93
Basic Definitions 94
The Algorithm 95
Performance Analysis 101
An Application 104
An Improved Randomized Approximation Algorithm for Maximum Triangle Packing 106
Introduction 106
Basic Definitions 107
Sketch of Hassin and Rubinstein's Algorithm 107
New Computation of P3 108
Analysis of the Approximation Ratio 117
Line Facility Location in Weighted Regions 118
Introduction 118
A Special Case 120
The General Case 122
Conclusion 128
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems 129
Introduction 129
Terminology and Notation 132
The NP-Completeness Proof 132
An Online Competitive Algorithm 136
A Lower Bound on the Competitive Ratio 137
Final Comments 138
Engineering Comparators for Graph Clusterings 140
Introduction 140
Preliminaries 141
Engineering Graph-Structural Comparison Measures 144
Extension of Node-Structural Measures 144
A Novel Approach for Measuring Graph-Structural Distance 145
Experiments and Evaluation 145
Initial- and Random Clusterings 146
Local Minimization 147
Real-World Scenario 149
Conclusion 150
On the Fast Searching Problem 152
Introduction 152
Properties 153
Trees 155
Bipartite Graphs 157
Cost Function 161
Conclusion and Open Problems 162
Confidently Cutting a Cake into Approximately Fair Pieces 164
Introduction 164
Other Related Work 166
The Original Balanced Allocation Lemma for Cake 167
The High Confidence Balanced Allocation Lemma 170
Initial Unsuccessful Approach 170
Copeland Voting Fully Resists Constructive Control 174
Introduction 175
Control 177
Definition of Control Problems 177
Overview of Results on Control 178
Two Subcases of Theorem 1: Constructive Control Via Adding Candidates 179
FPT Algorithm Schemes for Bounded-Case Control 181
Bribery 183
Conclusions 184
The Complexity of Power-Index Comparison 186
Introduction 186
The Power-Index Comparison Problem 187
Computational Complexity 188
Main Results 190
Conclusions and Open Problems 194
Facility Location Problems: A Parameterized View 197
Introduction 197
Facility Location Is in FPT 199
Finding Reduction Rules 199
Kernelization through Well-Quasi Orderings 200
Kernelization Refinements 201
Improving on Brute Force by Dynamic Programming 202
Further Improvements 202
Variants of Facility Location 203
Applications: The MDL Principle 204
Automizing the Production of XML Documents 204
Computational Biology 206
Conclusions and Further Research 207
Shortest Path Queries in Polygonal Domains 209
Introduction 209
Preliminaries 210
A Tessellation of P 212
Local Shortest Paths and Critical Sites 213
Our Algorithm 215
A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem 221
Introduction 221
Preliminaries 223
Algorithm Description 225
Approximation Analysis 230
Function c Satisfies the Quadrangle Inequality 232
Minimum Cost Homomorphism Dichotomy for Oriented Cycles 233
Introduction 233
Levels of Vertices in Oriented Paths and Cycles 235
k-Min-Max and (k,l)-Min-Max Orderings 236
Balanced Oriented Cycles 238
Dichotomy and Unbalanced Oriented Cycles 241
Minimum Leaf Out-Branching Problems 244
Introduction 244
MinLOB-DAG 245
Parameterizations of MinLOB 247
Solving MinLOB-PBGV 248
Discussion and Further Research 253
Graphs and Path Equilibria 256
Introduction 256
Dalographs and Equilibria 257
Binary Relations 259
Equilibrium Existence, Examples, and Application 261
Preservation of Equilibrium Existence 264
Sufficient Condition and Necessary Condition 266
Conclusion and Open Questions 267
No l Grid-Points in Spaces of Small Dimension 268
Introduction 268
No l Collinear Points 269
No (k + 2) Points in Affine k-Space or Linear (k+1)-Space 274
Concluding Remarks 278
The Secret Santa Problem 280
Introduction 280
Characterisation of Anonymity and Basic Results 282
Some Examples 283
A Polynomial Time Algorithm 284
Computational Results 285
Conclusion 287
Finding Optimal Refueling Policies in Transportation Networks 289
Introduction 289
The Optimal Refueling Policy Problems 290
Combinatorial Properties of Optimal [L,L] Refueling Policies 292
Solving the Optimal Refueling Policy Problems 297
Scale Free Interval Graphs 301
Introduction 301
Preliminaries 302
Scale Free Graph 303
Probability Distributions 304
New Model of Scale Free Interval Graphs 304
Scale Free Property 305
Clustering Coefficient 309
Concluding Remarks 311
On Representation of Planar Graphs by Segments 313
Introduction 313
Preliminaries 315
VFCR for 2-Connected Plane Graphs 316
st-Orientations of 3-Connected Planar Graphs and Their Applications in VFCR 317
Conclusion 324
An Optimal On-Line Algorithm for PreemptiveScheduling on Two Uniform Machinesin the $l_p$ Norm 325
Introduction 325
Preliminaries and Notations 327
Upper Bound 330
Lower Bound 334
An Optimal Strategy for Online Non-uniform Length Order Scheduling 337
Introduction 337
Related Work 338
Our Results 339
Definitions and Online Strategy Description 339
Competitive Ratio Definition 339
An Online Strategy 339
Basic Properties 340
Competitive Analysis 342
Conclusion 344
Large-Scale Parallel Collaborative Filtering for the Netflix Prize 346
Introduction 346
Problem Formulation 347
Our Approaches 348
ALS with Weighted--Regularization 349
Parallel ALS with Weighted--Regularization 350
Performance for the Netflix Prize Problem 352
Postprocessing 352
Experimental Results for ALS 352
Other Methods and Linear Blending 354
Related Work 354
Recommendation Systems 355
The Netflix Prize Approaches 355
Low-Rank Approximation 355
Concluding Remarks 356

Front Matter....Pages -
Double Partition: (6 + ε )-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs....Pages 1-1
Nash Bargaining Via Flexible Budget Markets....Pages 2-2
On the Minimum Hitting Set of Bundles Problem....Pages 3-14
Speed Scaling with a Solar Cell....Pages 15-26
Engineering Label-Constrained Shortest-Path Algorithms....Pages 27-37
New Upper Bounds on Continuous Tree Edge-Partition Problem....Pages 38-49
A Meeting Scheduling Problem Respecting Time and Space....Pages 50-59
Fixed-Parameter Algorithms for Kemeny Scores....Pages 60-71
The Distributed Wireless Gathering Problem....Pages 72-83
Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement....Pages 84-96
An Improved Randomized Approximation Algorithm for Maximum Triangle Packing....Pages 97-108
Line Facility Location in Weighted Regions....Pages 109-119
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems....Pages 120-130
Engineering Comparators for Graph Clusterings....Pages 131-142
On the Fast Searching Problem....Pages 143-154
Confidently Cutting a Cake into Approximately Fair Pieces....Pages 155-164
Copeland Voting Fully Resists Constructive Control....Pages 165-176
The Complexity of Power-Index Comparison....Pages 177-187
Facility Location Problems: A Parameterized View....Pages 188-199
Shortest Path Queries in Polygonal Domains....Pages 200-211
A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem....Pages 212-223
Minimum Cost Homomorphism Dichotomy for Oriented Cycles....Pages 224-234
Minimum Leaf Out-Branching Problems....Pages 235-246
Graphs and Path Equilibria....Pages 247-258
No l Grid-Points in Spaces of Small Dimension....Pages 259-270
The Secret Santa Problem....Pages 271-279
Finding Optimal Refueling Policies in Transportation Networks....Pages 280-291
Scale Free Interval Graphs....Pages 292-303
On Representation of Planar Graphs by Segments....Pages 304-315
An Optimal On-Line Algorithm for Preemptive Scheduling on Two Uniform Machines in the l p Norm....Pages 316-327
An Optimal Strategy for Online Non-uniform Length Order Scheduling....Pages 328-336
Large-Scale Parallel Collaborative Filtering for the Netflix Prize....Pages 337-348
Back Matter....Pages -

This volume constitutes the proceedings of the International Conference on Algorithmic Aspects in Information and Management, AAIM 2014, held in Vancouver, BC, Canada, in July 2014.The 30 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 45 submissions.

2010-02-18