Contemporary and Emerging Applications Volume II Chapman & Hall/CRC Computer and Information Science Series Series Editor: Sartaj Sahni Computer-Aided Graphing and Simulation Tools for AutoCAD Users P. A. Simionescu Integration of Services into Workflow Applications Paweł Czarnul Handbook of Graph Theory, Combinatorial Optimization, and Algorithms Krishnaiyan “KT” Thulasiraman, Subramanian Arumugam, Andreas Brandstädt, and Takao Nishizeki From Action Systems to Distributed Systems The Refinement Approach Luigia Petre and Emil Sekerinski Trustworthy Cyber-Physical Systems Engineering Alexander Romanovsky and Fuyuki Ishikawa X-Machines for Agent-Based Modeling FLAME Perspectives Mariam Kiran From Internet of Things to Smart Cities Enabling Technologies Hongjian Sun, Chao Wang, and Bashar I. Ahmad Evolutionary Multi-Objective System Design Theory and Applications Nadia Nedjah, Luiza De Macedo Mourelle, and Heitor Silverio Lopes Networks of the Future Architectures, Technologies, and Implementations Mahmoud Elkhodr, Qusay F. Hassan, and Seyed Shahrestani Computer Simulation A Foundational Approach Using Python Yahya E. Osais Internet of Things Challenges, Advances, and Applications Qusay F. Hassan, Atta ur Rehman Khan, and Sajjad A. Madani Handbook of Data Structures and Applications, Second Edition Dinesh P. Mehta and Sartaj Sahni Handbook of Approximation Algorithms and Metaheuristics, Second Edition Methodologies and Traditional Applications, Volume 1 Teofilo F. Gonzalez Handbook of Approximation Algorithms and Metaheuristics, Second Edition Contemporary and Emerging Applications, Volume 2 Teofilo F. Gonzalez For more information about this series please visit: https://www.crcpress.com/Chapman--HallCRC-Computer-and-Information-Science-Series/book-series/CHCOMINFSCI Handbook of Approximation Algorithms and Metaheuristics, Second Edition Contemporary and Emerging Applications Volume II Edited by Teofilo F. Gonzalez CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2018 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed on acid-free paper International Standard Book Number-13: 978-1-4987-6999-0 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material repro- duced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright. com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identifica- tion and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com TomywifeDorothy,andourchildren: Jeanmarie,Alexis,Julia,Teofilo,andPaolo. Contents Preface......................................................................... xi Contributors.................................................................. xiii 1 Introduction,Overview,andNotation........................................ 1 TeofiloF.Gonzalez SECTION I Computational Geometry and Graph Applications 2 ApproximationSchemesforMinimum-Costk-ConnectivityProblems inGeometricGraphs ...................................................... 29 ArturCzumajandAndrzejLingas 3 DilationandDetoursinGeometricNetworks ................................ 53 JoachimGudmundssonandChristianKnauer 4 TheWell-SeparatedPairDecompositionandItsApplications.................. 71 MichielSmid 5 CoveringwithUnitBalls................................................... 85 HosseinGhasemalizadehandMohammadrezaRazzazi 6 MinimumEdge-LengthRectangularPartitions............................... 97 TeofiloF.GonzalezandSiQingZheng 7 AutomaticPlacementofLabelsinMapsandDrawings....................... 111 KonstantinosG.KakoulisandIoannisG.Tollis 8 Complexity,ApproximationAlgorithms,andHeuristicsfor theCorridorProblems.................................................... 139 TeofiloF.GonzalezandArturoGonzalez-Gutierrez 9 ApproximateClustering .................................................. 153 RageshJaiswalandSandeepSen 10 MaximumPlanarSubgraph............................................... 171 GruiaCa˘linescuandCristinaG.Fernandes 11 DisjointPathsandUnsplittableFlow....................................... 187 StavrosG.Kolliopoulos vii viii Contents 12 Thek-ConnectedSubgraphProblem....................................... 213 ZeevNutov 13 Node-ConnectivitySurvivableNetworkProblems........................... 233 ZeevNutov 14 OptimumCommunicationSpanningTrees................................. 255 BangYeWu,ChuanYiTang,andKun-MaoChao 15 ActivationNetworkDesignProblems ...................................... 273 ZeevNutov 16 StochasticLocalSearchAlgorithmsfortheGraphColoringProblem .......... 299 MarcoChiarandini,IrinaDumitrescu,andThomasStützle 17 OnSolvingtheMaximumDisjointPathsProblemwith AntColonyOptimization................................................. 317 MariaJ.BlesaandChristianBlum 18 EfficientApproximationAlgorithmsinRandomIntersectionGraphs.......... 333 SotirisE.Nikoletseas,ChristoforosL.Raptopoulos,andPaulG.Spirakis 19 ApproximationAlgorithmsforFacilityDispersion........................... 347 S.S.Ravi,DanielJ.Rosenkrantz,andGiriK.Tayi SECTION II Large-Scale and Emerging Applications 20 Cost-EfficientMulticastRoutinginAdHocandSensorNetworks ............ 369 PedroM.RuizandIvanStojmenovic 21 ApproximationAlgorithmforClusteringinMobileAd-HocNetworks........ 383 LanWang,XianpingWang,andStephanOlariu 22 TopologyControlProblemsforWirelessAdHocNetworks .................. 419 GruiaCa˘linescu,ErrolL.Lloyd,andS.S.Ravi 23 QoSMultimediaMulticastRouting ........................................ 441 IonMandoiu,AlexOlshevsky,andAlexZelikovsky 24 OverlayNetworksforPeer-to-PeerNetworks ............................... 459 AndréaW.Richa,ChristianScheideler,andStefanSchmid 25 DataBroadcastsonMultipleWirelessChannels:Exactand Time-OptimalSolutionsforUniformDataandHeuristics forNonuniformData..................................................... 483 AlanA.Bertossi,CristinaM.Pinotti,andRomeoRizzi 26 StrategiesforAggregatingTime-DiscountedInformationin SensorNetworks......................................................... 505 XianpingWangandStephanOlariu 27 ApproximationandExactAlgorithmsforOptimallyPlacingaLimited NumberofStorageNodesinaWirelessSensorNetwork ..................... 541 GianlorenzoD’Angelo,AlfredoNavarra,andCristinaM.Pinotti Contents ix 28 ApproximationAlgorithmsforthePrimerSelection,PlantedMotif Search,andRelatedProblems ............................................. 567 SudhaBalla,JaimeDavila,MariusNicolae,andSanguthevarRajasekaran 29 DynamicandFractionalProgramming-BasedApproximationAlgorithms forSequenceAlignmentwithConstraints .................................. 599 AbdullahN.ArslanandÖmerEg˘eciog˘lu 30 ApproximationAlgorithmsfortheSelectionofRobustTagSNPs ............. 617 Yao-TingHuang,KuiZhang,TingChen,andKun-MaoChao 31 Large-ScaleGlobalPlacement ............................................. 635 JasonCongandJosephR.Shinnerl 32 Histograms,Wavelets,Streams,andApproximation......................... 673 SudiptoGuha 33 ColorQuantization....................................................... 691 ZhigangXiang 34 AGSO-BasedSwarmAlgorithmforOdorSourceLocalizationin TurbulentEnvironments ................................................. 711 JosephThomasandDebasishGhose 35 DigitalReputationforVirtualCommunities ................................ 739 RobertoBattitiandAnuragGarg 36 ApproximationforInfluenceMaximization................................. 757 JingYuan,WeiliWu,andWenXu 37 ApproximationandHeuristicsforCommunityDetection.................... 761 JingYuan,WeiliWu,andSaratChandraVaranasi Index......................................................................... 771