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

    AAM Volume I, Table of Contents

    AAM First Edition, Table of Contents

    AAM First Edition. List of Contibutors (Alphabetic wrt first name)