Approximation Algorithms and Metaheuristics
Volume II: Contemporary and Emerging Applications
Editor: Teofilo F. Gonzalez
Second Edition, March 2018
(teo@cs.ucsb.edu)
Table of Contents
Chapter 1:
Introduction, Overview and Notation
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Part I: Computational Geometry and Graph Applications
Chapter 2:
Approximation Schemes for Minimum-Cost k-Connectivity Problems in Geometric Graphs
Artur Czumaj,
University of Warwick, Coventry, United Kindom
Andrzej Lingas,
Lund University, Lund, Sweden
Chapter 3:
Dilation and Detours in Geometric Networks
Joachim Gudmundsson,
University of Sydney, Sydney, Australia
Christian Knauer,
Universität Bayreuth, Germany
Chapter 4:
The Well-Separated Pair Decomposition and Its Applications
Michiel Smid,
Carleton University, Ottawa, Ontario, Canada
Chapter 5:
Covering with Unit Balls
Hossein Ghasemalizadeh,
Shahid Bahonar University, Kerman, Iran
Mohammadreza Razzazi,
Amirkabir University of Technology, Tehran, Iran
Chapter 6:
Minimum Edge Length Rectangular Partitions
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Si Qing Zheng,
University of Texas at Dallas, Richardson, TX, USA
Chapter 7:
Automatic Placement of Labels in Maps and Drawings
Konstantinos G. Kakoulis,
Western Macedonia University of Applied Sciences, Greece
Ioannis G. Tollis,
University of Crete, Greece
Chapter 8:
Complexity, Approximation Algorithms, and Heuristics for the Corridor Problems
Teofilo F. Gonzalez,
University of California, Santa Barbara, CA, USA
Arturo Gonzalez-Gutierrez,
Universidad Autónoma de Querétaro, Querétaro, Qro., 76010, México
Chapter 9:
Approximate Clustering
Ragesh Jaiswal,
Indian Institute of Technology Delhi, New Delhi, India
Sandeep Sen,
Indian Institute of Technology Delhi, New Delhi, India
Chapter 10:
Maximum Planar Subgraph
Gruia Calinescu,
Illinois Institute of Technology, Chicago, IL USA
Cristina G. Fernandes,
University of Sao Paulo, Sao Paulo, Brazil
Chapter 11:
Disjoint Paths and Unsplittable Flow
Stavros G. Kolliopoulos,
National and Kapodistrian University of Athens, Athens, Greece
Chapter 12:
The $k$-Connected subgraph Problem
Zeev Nutov,
The Open University of Israel, Israel
Chapter 13:
Node-Connectivity Survivable Network Problems
Zeev Nutov,
The Open University of Israel, Israel
Chapter 14:
Optimum Communication Spanning Trees
Bang Ye Wu,
National Chung Cheng University, Chiayi County, Taiwan, ROC
Chuan Yi Tang,
National Tsing Hua University, Hsinchu, Taiwan, ROC
Kun-Mao Chao,
National Taiwan University, Taipei, Taiwan, ROC
Chapter 15:
Activation Network Design Problems
Zeev Nutov,
The Open University of Israel, Israel
Chapter 16:
Stochastic Local Search Algorithms for the Graph Colouring Problem
Marco Chiarandini,
University of Southern Denmark, Odense, Denmark
Irina Dumitrescu,
University of New South Wales, Sydney, Australia
Thomas Stützle,
Université Libre de Bruxelles, Brussels, Belgium
Chapter 17:
On Solving the Maximum Disjoint Paths Problem with Ant Colony Optimization
Maria J. Blesa,
Universitat Politècnica de Catalunya, Barcelona, Spain
Christian Blum,
Universitat Politècnica de Catalunya, Barcelona, Spain
Chapter 18:
Efficient Approximation Algorithms in Random Intersection Graphs
Sotiris Nikoletseas,
Patras University, Patras, Greece
Christoforos L. Raptopoulos,
Patras University, Patras, Greece
Paul Spirakis,
Patras University, Patras, Greece
Chapter 19:
Approximation Algorithms for Facility Dispersion
S. S. Ravi,
Biocomplexity Institute of Virginia Tech, Blacksbury, VA, USA
Daniel J. Rosenkrantz,
University at Albany -- SUNY, Albany, NY USA
Giri K. Tayi,
University at Albany -- SUNY, Albany, NY USA
Part II: Large-Scale and Emerging Applications
Chapter 20:
Cost-Efficient Multicast Routing in Ad Hoc and Sensor Networks
Pedro M. Ruiz,
University of Murcia, Espinardo, Murcia, Spain
Ivan Stojmenovic,
University of Ottawa, Ottawa, Ontario, Canada
Chapter 21:
Approximation Algorithm for Clustering in Ad-hoc Networks
Lan Wang,
Old Dominion University, Norfolk, VA, USA
Xianping Wang,
Old Dominion University, Norfolk, VA, USA
Stephan Olariu,
Old Dominion University, Norfolk, VA, USA
Chapter 22:
Topology Control Problems for Wireless Ad~hoc Networks
Gruia Calinescu,
Illinois Institute of Technology, Chicago, IL USA
Errol L. Lloyd,
University of Delaware, Newark, DE, USA
S. S. Ravi,
Biocomplexity Institute of Virginia Tech, Blacksbury, VA, USA
Chapter 23:
QoS Multimedia Multicast Routing
Ion Mandoiu,
University of Connecticut, Storrs, CT, USA
Alex Olshevsky,
Boston University, Boston, MA, USA
Alexander Zelikovsky,
Georgia State University, Atlanta, GA, USA
Chapter 24:
Overlay Networks for Peer-to-Peer Networks
Andréa W. Richa,
Arizona State University, Tempe, AZ, USA
Christian Scheideler,
University of Paderborn, Paderborn, Germany
Chapter 25:
Scheduling Data Broadcasts on Wireless Channels: Exact Solutions
% 67
Alan A. Bertossi,
University of Bologna, Bologna, Italy
M. Cristina Pinotti,
University of Perugia, Perugia, Italy
Romeo Rizzi,
University of Verona, Verona, Italy
Chapter 26:
Strategies for Aggregating Time-discounted Information in Sensor
Networks
Xianping Wang,
Old Dominion University, Norfolk, VA, USA
Stephan Olariu,
Old Dominion University, Norfolk, VA, USA
Chapter 27:
Approximation and exact algorithms for optimally placing a limited
number of storage nodes in a wireless sensor network
Gianlorenzo D'Angelo,
Gran Sasso Science Institute, L'Aquila, Italy
Alfredo Navarra,
University of Perugia, Perugia, Italy
M. Cristina Pinotti,
University of Perugia, Perugia, Italy
Chapter 28:
Approximation Algorithms for the Primer Selection, Planted Motif Search, and Related Problems
Sudha Balla,
Univ. of Connecticut, Storrs, CT USA
Jaime Davila,
Univ. of Connecticut, Storrs, CT USA
Marius Nicolae,
Univ. of Connecticut, Storrs, CT USA
Sanguthevar Rajasekaran,
Univ. of Connecticut, Storrs, CT USA
Chapter 29:
Dynamic and Fractional Programming based Approximation Algorithms for Sequence Alignment with Constraints
Abdullah N. Arslan,
Texas A & M University, Commerce, TX, USA
Ömer Egecioglu,
University of California, Santa Barbara, CA, USA
Chapter 30:
Approximation Algorithms for the Selection of Robust Tag SNPs
Yao-Ting Huang,
National Chung Cheng University, Chiayi County, Taiwan, ROC
Kui Zhang,
Michigan Technological University, USA
Ting Chen,
Tsinghua University, China
Kun-Mao Chao,
National Taiwan University, Taipei, Taiwan, ROC
Chapter 31:
Large-Scale Global Placement
Jason Cong,
University of California, Los Angeles, CA, USA
Joseph R. Shinnerl,
Mentor Graphics Corporation, Freemont, CA, USA
Chapter 32:
Histograms, Wavelets, Streams and Approximation
Sudipto Guha,
Univ. of Pennsylvania, Philadelphia, PA, USA
Chapter 33:
Color Quantization
Zhigang Xiang,
Queens College of the City University of New York, Flushing, NY, USA
Chapter 34:
A GSO based Swarm Algorithm for Odor Source Localization in
Turbulent Environments
Joseph Thomas,
Indian Institute of Science, Bangalore, India
Debasish Ghose,
Indian Institute of Science, Bangalore, India
Chapter 35:
Digital Reputation for Virtual Communities
Roberto Battiti,
University of Trento, Trento, Italy
Anurag Garg,
University of Trento, Trento, Italy
Chapter 36:
Approximation for Influence Maximization
Jing Yuan,
University of Texas at Dallas, Richardson, TX, USA
Weili Wu,
University of Texas at Dallas, Richardson, TX, USA
Wen Xu,
Texas Woman's University, Denton, TX, USA
Chapter 37:
Approximation and Heuristics for Community Detection
Jing Yuan,
University of Texas at Dallas, Richardson, TX, USA
Weili Wu,
University of Texas at Dallas, Richardson, TX, USA
Sarat Chandra Varanasi,
University of Texas at Dallas, Richardson, TX, USA