This book will serve as a reference, presenting state-of-the-art research on theoretical aspects of optimal sensor coverage problems. Readers will find it a useful tool for furthering developments on theory and applications of optimal coverage; much of the content can serve as material for advanced topics courses at the graduate level. The book is well versed with the hottest research topics such as Lifetime of Coverage, Weighted Sensor Cover, k-Coverage, Heterogeneous Sensors, Barrier, Sweep and Partial Coverage, Mobile Sensors, Camera Sensors and Energy-Harvesting Sensors, and more. Topics are introduced in a natural order from simple covers to connected covers, to the lifetime problem. Later, the book begins revisiting earlier problems ranging from the introduction of weights to coverage by k sensors and partial coverage, and from sensor heterogeneity to novel problems such as the barrier coverage problem. The book ends with coverage of mobile sensors, camera sensors, energy-harvesting sensors, underwater sensors, and crowdsensing.

This book is a collection of articles studying various Steiner tree prob lems with applications in industries, such as the design of electronic cir cuits, computer networking, telecommunication, and perfect phylogeny. The Steiner tree problem was initiated in the Euclidean plane. Given a set of points in the Euclidean plane, the shortest network interconnect ing the points in the set is called the Steiner minimum tree. The Steiner minimum tree may contain some vertices which are not the given points. Those vertices are called Steiner points while the given points are called terminals. The shortest network for three terminals was first studied by Fermat (1601-1665). Fermat proposed the problem of finding a point to minimize the total distance from it to three terminals in the Euclidean plane. The direct generalization is to find a point to minimize the total distance from it to n terminals, which is still called the Fermat problem today. The Steiner minimum tree problem is an indirect generalization. Schreiber in 1986 found that this generalization (i.e., the Steiner mini mum tree) was first proposed by Gauss."

Introduction The exponential scaling of feature sizes in semiconductor technologies has side-effects on layout optimization, related to effects such as inter connect delay, noise and crosstalk, signal integrity, parasitics effects, and power dissipation, that invalidate the assumptions that form the basis of previous design methodologies and tools. This book is intended to sample the most important, contemporary, and advanced layout opti mization problems emerging with the advent of very deep submicron technologies in semiconductor processing. We hope that it will stimulate more people to perform research that leads to advances in the design and development of more efficient, effective, and elegant algorithms and design tools. Organization of the Book The book is organized as follows. A multi-stage simulated annealing algorithm that integrates floorplanning and interconnect planning is pre sented in Chapter 1. To reduce the run time, different interconnect plan ning approaches are applied in different ranges of temperatures. Chapter 2 introduces a new design methodology - the interconnect-centric design methodology and its centerpiece, interconnect planning, which consists of physical hierarchy generation, floorplanning with interconnect planning, and interconnect architecture planning. Chapter 3 investigates a net-cut minimization based placement tool, Dragon, which integrates the state of the art partitioning and placement techniques."

This book contains a collection of survey papers in the areas of algorithms, lan guages and complexity, the three areas in which Professor Ronald V. Book has made significant contributions. As a fonner student and a co-author who have been influenced by him directly, we would like to dedicate this book to Professor Ronald V. Book to honor and celebrate his sixtieth birthday. Professor Book initiated his brilliant academic career in 1958, graduating from Grinnell College with a Bachelor of Arts degree. He obtained a Master of Arts in Teaching degree in 1960 and a Master of Arts degree in 1964 both from Wesleyan University, and a Doctor of Philosophy degree from Harvard University in 1969, under the guidance of Professor Sheila A. Greibach. Professor Book's research in discrete mathematics and theoretical com puter science is reflected in more than 150 scientific publications. These works have made a strong impact on the development of several areas of theoretical computer science. A more detailed summary of his scientific research appears in this volume separately."

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have important applications in communication networks, especially in wireless networks, as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.

2. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3. Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ., . . . . 60 4. Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 A Simple Proof for a Result of Ollerenshaw on Steiner Trees . . . . . . . . . . 68 Xiufeng Du, Ding-Zhu Du, Biao Gao, and Lixue Qii 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2. In the Euclidean Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3. In the Rectilinear Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4. Discussion . . . . . . . . . . . . -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Optimization Algorithms for the Satisfiability (SAT) Problem . . . . . . . . . 72 Jun Gu 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2. A Classification of SAT Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7:3 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV 4. Complete Algorithms and Incomplete Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5. Optimization: An Iterative Refinement Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6. Local Search Algorithms for SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 7. Global Optimization Algorithms for SAT Problem . . . . . . . . . . . . . . . . . . . . . . . . 106 8. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 9. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Ergodic Convergence in Proximal Point Algorithms with Bregman Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Osman Guier 1. Introduction . . .: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2. Convergence for Function Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 3. Convergence for Arbitrary Maximal Monotone Operators . . . . . . . . . . . .

With the rapid growth of bandwidth demand from network users and the advances in optical technologies, optical networks with multiterabits per-second capacity has received significant interest from both researchers and practitioners. Optical networks deployment raises a number of challenging problems that require innovative solutions, including net work architectures, scalable and fast network management, resource efficient routing and wavelength assignment algorithms, QoS support and scheduling algorithms, and switch and router architectures. In this book, we put together some important developments in this exiting area during last several years. Some of the articles are research papers and some are surveys. All articles were reviewed by two reviewers. The paper, "On Dynamic Wavelength Assignment in WDM Optical Networks," by Alanyali gives an overview of some issues in the analy sis and synthesis of dynamic wavelength assignment policies for optical WDM networks and illustrates a new method of analysis. The paper by Ellinas and Bala, "Wavelength Assignment Algorithms for WDM Ring Architectures," presents two optimal wavelength assignment algorithms that assign the minimum number of wavelengths between nodes on WDM rings to achieve full mesh connectivity. In the paper, "Optimal Placement of Wavelength Converters in WDM Networks for Parallel and Distributed Computing Systems," Jia et al."

A basic problem for the interconnection of communications media is to design interconnection networks for specific needs. For example, to minimize delay and to maximize reliability, networks are required that have minimum diameter and maximum connectivity under certain conditions. The book provides a recent solution to this problem. The subject of all five chapters is the interconnection problem. The first two chapters deal with Cayley digraphs which are candidates for networks of maximum connectivity with given degree and number of nodes. Chapter 3 addresses Bruijn digraphs, Kautz digraphs, and their generalizations, which are candidates for networks of minimum diameter and maximum connectivity with given degree and number of nodes. Chapter 4 studies double loop networks, and Chapter 5 considers broadcasting and the Gossiping problem. All the chapters emphasize the combinatorial aspects of network theory. Audience: A vital reference for graduate students and researchers in applied mathematics and theoretical computer science.

The switching net.work is an important. classic research area in t.ele- communication and comput.er net.works. It.s import.ancc st.ems from both theory and practice. In fact, some open problems, such as Benes conjec- ture on shuffle-exchange networks and Chung-Rmis conjecture on multi- rate rearrangeability, still attract many researchers and the further de- velopment in optical networks requires advanced technology in optical switching networks. In 1997, we had a workshop in switching networks held in NSF Sci- ence and Technology Center in Discrete Mathematics and Theoretical Computer Science (DIMACS), at Princeton University. This workshop was very successful. Many participants wished to have a similar activity every two or three years. This book is a result of such a wish. We are putting together SOllle important developments in this area during last. several years, including articles ill fault-tolerance, rearrang{~ability. non- blocking, optical networks. random permutation generat.ioll. and layout complexity. SOlllC of thos(~ art ides are research papers alld SOIllC an' sur- veys. All articles were reviewed. We would like to uWlItioll two special problems studied in those articles.

This book identifies vulnerabilities in the physical layer, the MAC layer, the IP layer, the transport layer, and the application layer, of wireless networks, and discusses ways to strengthen security mechanisms and services. Topics covered include intrusion detection, secure PHY/MAC/routing protocols, attacks and prevention, immunization, key management, secure group communications and multicast, secure location services, monitoring and surveillance, anonymity, privacy, trust establishment/management, redundancy and security, and dependable wireless networking.

This is a supplementary volume to the major three-volume Handbook of Combinatorial Optimization set. It can also be regarded as a stand-alone volume presenting chapters dealing with various aspects of the subject in a self-contained way.

Combinatorial optimization algorithms are used in many applications including the design, management, and operations of communication networks. The objective of this book is to advance and promote the theory and applications of combinatorial optimization in communication networks. Each chapter of the book is written by an expert dealing with theoretical, computational, or applied aspects of combinatorial optimization. Topics covered in the book include the combinatorial optimization problems arising in optical networks, wireless ad hoc networks, sensor networks, mobile communication systems, and satellite networks. A variety of problems are addressed using combinatorial optimization techniques, ranging from routing and resource allocation to QoS provisioning.

Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, air line crew scheduling, corporate planning, computer-aided design and man ufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, alloca tion of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addi tion, linear programming relaxations are often the basis for many approxi mation algorithms for solving NP-hard problems (e.g. dual heuristics)."

This book provides an introduction to the mathematical theory of optimization. It emphasizes the convergence theory of nonlinear optimization algorithms and applications of nonlinear optimization to combinatorial optimization. Mathematical Theory of Optimization includes recent developments in global convergence, the Powell conjecture, semidefinite programming, and relaxation techniques for designs of approximation solutions of combinatorial optimization problems.

Graduate students and researchers in applied mathematics, optimization, engineering, computer science, and management science will find this book a useful reference which provides an introduction to applications and fundamental theories in nonlinear combinatorial optimization. Nonlinear combinatorial optimization is a new research area within combinatorial optimization and includes numerous applications to technological developments, such as wireless communication, cloud computing, data science, and social networks. Theoretical developments including discrete Newton methods, primal-dual methods with convex relaxation, submodular optimization, discrete DC program, along with several applications are discussed and explored in this book through articles by leading experts.

Wireless networking enables two or more computers to communicate using standard network protocols without network cables. Since their emergence in the 1970s, wireless networks have become increasingly pop ular in the computing industry. In the past decade, wireless networks have enabled true mobility. There are currently two versions of mobile wireless networks. An infrastructure network contains a wired backbone with the last hop being wireless. The cellular phone system is an exam ple of an infrastructure network. A multihop ad hoc wireless network has no infrastructure and is thus entirely wireless. A wireless sensor network is an example of a multihop ad hoc wireless network. Ad hoc wireless networking is a technique to support robust and ef ficient operation in mobile wireless networks by incorporating routing functionality into mobile hosts. This technique will be used to realize the dream of "anywhere and anytime computing," which is termed mo bile computing. Mobile computing is a new paradigm of computing in which users carrying portable devices have access to shared infrastruc ture in any location at any time. Mobile computing is a very challenging topic for scientists in computer science and electrical engineering. The representative system for ad hoc wireless networking is called MANET, an acronym for "Mobile Ad hoc NETworks." MANET is an autonomous system consisting of mobile hosts connected by wireless links which can be quickly deployed."

Techniques and principles of minimax theory play a key role in many areas of research, including game theory, optimization, and computational complexity. In general, a minimax problem can be formulated as min max f(x, y) (1) ",EX !lEY where f(x, y) is a function defined on the product of X and Y spaces. There are two basic issues regarding minimax problems: The first issue concerns the establishment of sufficient and necessary conditions for equality minmaxf(x,y) = maxminf(x,y). (2) "'EX !lEY !lEY "'EX The classical minimax theorem of von Neumann is a result of this type. Duality theory in linear and convex quadratic programming interprets minimax theory in a different way. The second issue concerns the establishment of sufficient and necessary conditions for values of the variables x and y that achieve the global minimax function value f(x*, y*) = minmaxf(x, y). (3) "'EX !lEY There are two developments in minimax theory that we would like to mention.

The Volume on Advances in Steiner Trees is divided into two sections. The first section of the book includes papers on the general geometric Steiner tree problem in the plane and higher dimensions. The second section of the book includes papers on the Steiner problem on graphs. The general geometric Steiner tree problem assumes that you have a given set of points in some d-dimensional space and you wish to connect the given points with the shortest network possible. The given set ofpoints are 3 Figure 1: Euclidean Steiner Problem in E usually referred to as terminals and the set ofpoints that may be added to reduce the overall length of the network are referred to as Steiner points. What makes the problem difficult is that we do not know a priori the location and cardinality ofthe number ofSteiner points. Thus)the problem on the Euclidean metric is not known to be in NP and has not been shown to be NP-Complete. It is thus a very difficult NP-Hard problem.

Following the pattern of the Internet growth in popularity, started in the early 1990s, the current unprecedented expansion of wireless technology promises to have an even greater effect on how people communicate and interact, with considerable socio-economic impact all over the world. The driving force behind this growth is the remarkable progress in component miniaturization, integration, and also devel- ments in waveforms, coding, and communication protocols. Besides established infrastructurebased wireless networks (cellular, WLAN, sat- lite) ad-hoc wireless networks emerge as a new platform for distributed applications and for personal communication in scenarios where deploying infrastructure is not feasible. In ad-hoc wireless networks, each node is capable of forwarding packets on behalf of other nodes, so that multi-hop paths provide end-to-end connectivity. The increased flexibility and mobility of ad-hoc wireless networks are favored for appli- tions in law enforcement, homeland defense and military. In a world where wireless networks become increasingly interoperable with each other and with the high-speed wired Internet, personal communication systems will transform into universal terminals with instant access to variate content and able of handle demanding tasks, such as multimedia and real-time video. With users roaming between networks, and with wide variation in wireless link quality even in a single domain, the communications terminal must continue to provide a level of Quality of Service that is acceptable to the user and conforms to a contracted Service Level Agreement.

Multiwavelength Optical Networks systematically studies the major research issues in WDM (Wavelength Division Multiplexing) optical networks, such as routing and wavelength assignment, QoS multicast routing, design of logical topologies, and placement of wavelength converters. The book consists of two parts. The first part studies the fundamental concepts and principles of WDM networks. The second part discusses advanced and research issues of WDM networks.
The authors of the book have many years of working experience in the areas of computer networks and network optimization. The book discusses many difficult issues of WDM networks in a very comprehensive way. For each problem, there is a background discussion, and then the mathematical formulation, followed by the solutions.

This book is intended to be used as a textbook for graduate students studying theoretical computer science. It can also be used as a reference book for researchers in the area of design and analysis of approximation algorithms. Design and Analysis of Approximation Algorithms is a graduate course in theoretical computer science taught widely in the universities, both in the United States and abroad. There are, however, very few textbooks available for this course. Among those available in the market, most books follow a problem-oriented format; that is, they collected many important combinatorial optimization problems and their approximation algorithms, and organized them based on the types, or applications, of problems, such as geometric-type problems, algebraic-type problems, etc. Such arrangement of materials is perhaps convenient for a researcher to look for the problems and algorithms related to his/her work, but is difficult for a student to capture the ideas underlying the various algorithms. In the new book proposed here, we follow a more structured, technique-oriented presentation. We organize approximation algorithms into different chapters, based on the design techniques for the algorithms, so that the reader can study approximation algorithms of the same nature together. It helps the reader to better understand the design and analysis techniques for approximation algorithms, and also helps the teacher to present the ideas and techniques of approximation algorithms in a more unified way.

This book provides a reference tool for the increasing number of scientists whose research is related to sensor network security. It is organised into sections, each including chapters exploring a specific topic. Topics covered include network design and modeling, network management, data management, security and applications.

Introductory courses in combinatorial optimization are popular at the upper undergraduate/graduate levels in computer science, industrial engineering, and business management/OR, owed to its wide applications in these fields. There are several published textbooks that treat this course and the authors have used many of them in their own teaching experiences. This present text fills a gap and is organized with a stress on methodology and relevant content, providing a step-by-step approach for the student to become proficient in solving combinatorial optimization problems. Applications and problems are considered via recent technology developments including wireless communication, cloud computing, social networks, and machine learning, to name several, and the reader is led to the frontiers of combinatorial optimization. Each chapter presents common problems, such as minimum spanning tree, shortest path, maximum matching, network flow, set-cover, as well as key algorithms, such as greedy algorithm, dynamic programming, augmenting path, and divide-and-conquer. Historical notes, ample exercises in every chapter, strategically placed graphics, and an extensive bibliography are amongst the gems of this textbook.

This volume constitutes the proceedings of the 12th International Conference on Algorithmic Aspects in Information and Management, AAIM 2018, held in Dallas, Texas, USA, in December 2018. The 25 full papers presented were carefully reviewed and selected. The papers deal with current trends of research on algorithms, data structures, operation research, combinatorial optimization and their applications.

This book constitutes the thoroughly refereed proceedings of the National Conference of Theoretical Computer Science, NCTCS 2017, held in Wuhan, Hubei, China, in October 2017. The 25 full papers presented were carefully reviewed and selected from 84 submissions. They present relevant trends of current research in the area of algorithms and complexity, software theory and method, data science and machine learning theory.