Search

This book constitutes the refereed proceedings of the 17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022, held as a virtual event, in September 2022. The 33 full papers were carefully reviewed and selected from 75 submissions. The main themes of the selected papers are computability, complexity, algorithms, information theory and their extensions to machine learning theory, and foundations of artificial intelligence.

This volume constitutes the proceedings of the 14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020, held in Jinhua, China in August 2020. The 39 full papers and 17 short papers presented were carefully reviewed and selected from 76 submissions. The papers deal with emerging important algorithmic problems with a focus on the fundamental background, theoretical technology development, and real-world applications associated with information and management analysis, modeling and data mining. Special considerations are given to algorithmic research that was motivated by real-world applications.

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.

This volume constitutes the proceedings of the 13th International Conference on Algorithmic Aspects in Information and Management, AAIM 2019, held in Bejing, China in August 2019. The 31 full papers presented were carefully reviewed and selected. The papers deal with most aspects of theoretical computer science and their applications. Special considerations are given to algorithmic research that is motivated by real-world applications.

This book constitutes the proceedings of the 25th International Conference on Computing and Combinatorics, COCOON 2019, held in Xi'an, China, in July 2019. The 55 papers presented in this volume were carefully reviewed and selected from 124 submissions. The papers cover various topics, including algorithm design, approximation algorithm, graph theory, complexity theory, problem solving, optimization, computational biology, computational learning, communication network, logic, and game theory.

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 volume presents selected papers from a three-day workshop held during the DIMACS special years on Mathematical Support for Molecular Biology. Participants from the world over attended, giving the workshop an important international component. The study of discrete mathematics and optimization with medical applications is emerging as an important new research area. Significant applications have been found in medical research, for example in radiosurgical treatment planning, virtual endoscopy, and more. This volume presents a substantive cross-section of active research topics ranging from medical imaging to human anatomy modeling, from gamma knife treatment planning to radiation therapy, and from epileptic seizures to DNA screening. This book is an up-to-date resource reflecting current research directions.

Time division multiplexing (TDM) has been the fundamental basis for adding capacity to digital telecommunications networks for decades. However, within the past two years, wavelength division multiplexing (WDM) has been emerging as an important and widely deployed complement to TDM. Sales of systems based on the new technology have risen at breathtaking speed. The driving force behind this sales explosion was the unexpected rapid exhaustion of long distance fiber network capacity. This fiber exhaust, combined with favorable economics for WDM, led to the use of this technology over other alternatives. The WDM deployment raises fundamental and challenging problems that require novel and innovative solutions. This volume presents papers from an interdisciplinary workshop held at DIMACS on multichannel optical networks. Leading computer science theorists and practitioners discussed admissions control, routing and channel assignment, multicasting and protection, and fault-tolerance. The book features application of theoretical and/or algorithmical results to practical problems and addresses the influence of practical problems to theoretical/algorithmic studies. The volume can serve as a text for an advanced course in computer science, networking, and operations research.

This book constitutes the refereed proceedings of the 9th International Conference on Combinatorial Optimization and Applications, COCOA 2015, held in Houston, TX, USA, in December 2015. The 59 full papers included in the book were carefully reviewed and selected from 125 submissions. Topics covered include classic combinatorial optimization; geometric optimization; network optimization; applied optimization; complexity and game; and optimization in graphs.

Praise for the First Edition'... complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity.'—Zentralblatt MATH A thorough revision based on advances in the field of computational complexity and readers'feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science Additional exercises at varying levels of difficulty to further test comprehension of the presented material End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

This book constitutes the refereed proceedings of the 8th International Conference on Combinatorial Optimization and Applications, COCOA 2014, held on the island of Maui, Hawaii, USA, in December 2014. The 56 full papers included in the book were carefully reviewed and selected from 133 submissions. Topics covered include classic combinatorial optimization; geometric optimization; network optimization; optimization in graphs; applied optimization; CSoNet; and complexity, cryptography, and games.

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.

This book constitutes the refereed proceedings of the 19th International Conference on Computing and Combinatorics, COCOON 2013, held in Hangzhou, China, in June 2013. The 56 revised full papers presented were carefully reviewed and selected from 120 submissions. There was a co-organized workshop on discrete algorithms of which 8 short papers were accepted and a workshop on computational social networks where 12 papers out of 25 submissions were accepted.

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. dualheuristics).

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. dualheuristics).

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.

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.

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.

This book constitutes the refereed proceedings of the 17th Annual International Conference on Computing and Combinatorics, held in Dallas, TX, USA, in August 2011. The 54 revised full papers presented were carefully reviewed and selected from 136 submissions. Topics covered are algorithms and data structures; algorithmic game theory and online algorithms; automata, languages, logic, and computability; combinatorics related to algorithms and complexity; complexity theory; computational learning theory and knowledge discovery; cryptography, reliability and security, and database theory; computational biology and bioinformatics; computational algebra, geometry, and number theory; graph drawing and information visualization; graph theory, communication networks, and optimization; parallel and distributed computing.

This book constitutes the refereed proceedings of the 5th International Conference on Combinatorial Optimization and Applications, COCOA 2011, held in Zhangjiajie, China, in August 2011. The 43 revised full papers were carefully reviewed and selected from 65 submissions. The papers cover a broad range of topics in combinatorial optimization and applications focussing on experimental and applied research of general algorithmic interest and research motivated by real-world problems.

This book constitutes the refereed proceedings of the Third International Conference on Combinatorial Optimization and Applications, COCOA 2009, held in Huangshan, China, in June 2009. The 50 revised full papers were carefully reviewed and selected from 103 submissions. The papers feature original research in the areas of combinatorial optimization - both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

This book constitutes the refereed proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, held in Honolulu, Hawaii, USA in December 2009. The 120 revised full papers presented were carefully reviewed and selected from 279 submissions for inclusion in the book. This volume contains topics such as algorithms and data structures, approximation algorithms, combinatorial optimization, computational biology, computational complexity, computational geometry, cryptography, experimental algorithm methodologies, graph drawing and graph algorithms, internet algorithms, online algorithms, parallel and distributed algorithms, quantum computing and randomized algorithms.

This book constitutes the refereed proceedings of the Second International Conference on Combinatorial Optimization and Applications, COCOA 2008, held in St. John's, Canada, in August 2008. The 44 revised full papers were carefully reviewed and selected from 84 submissions. The papers feature original research in the areas of combinatorial optimization -- both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied ma- ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, a- line crew scheduling, corporate planning, computer-aided design and m- 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, allo- 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 discov- ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These al- 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 ad- tion, linear programming relaxations are often the basis for many appro- mation algorithms for solving NP-hard problems (e.g. dual heuristics).

The ICTCA conference provides an interdisciplinary forum for active researchers in academia and industry who are of varying backgrounds to discuss the state-of-the-art developments and results in theoretical and computational acoustics and related topics. The papers presented at the meeting cover acoustical problems of common interest across disciplines and their accurate mathematical and numerical modelling.The present book collects papers that were presented at the 4th meeting and printed in the Journal of Computational Acoustics. There are about 120 full research articles on various subjects, such as wave propagation theory and numerical modelling, sound propagation, vibrations and noise generation, underwater acoustics, engineering seismology, ultrasonic field synthesis and modelling, as well as computational methods, inverse problems and tomography, shallow water acoustics and environmental/bottom parameter extraction. A CD-Rom is attached that allows readers to browse through articles and print those of interest to them.

INDOCRYPT 2001, the Second Annual Crypto Conference, is proof of the s- ni?cant amount of enthusiasm generated among Indian as well as International crypto communities. INDOCRYPT 2001 was organized by the Indian Institute of Technology, Madras and the Institute of Mathematical Sciences, also located in Madras (now Chennai). This event was enthusiastically co-sponsored by eAl- traz ConsultingPrivate Ltd, Chennai, Odyssey Technologies Ltd, Chennai, and Shanmuga Arts Science Technology and Research Academy (SASTRA), Th- javur. The Program Committee Co-chair, Prof.C.Pandu Rangan was responsible for local organization and registration. The Program Committee considered 77 papers and selected 31 papers for presentation. These papers were selected on the basis of perceived originality, quality, and relevance to the?eld of cryptography. The proceedings include the revised version of the accepted papers. Revisions were not checked as to their contents and authors bear full responsibility for the contents of their submissions. The selection of papers is a very challengingand demandingtask. We wish to thank the Program Committee members who did an excellent job in reviewing the submissions in spite of severe time constraints imposed by the tight p- cessingschedule. Each submission was reviewed by at least three referees (only a few by two). The Program Committee was ably assisted by a large number of reviewers in their area of expertise. The list of reviewers has been provided separately. Our thanks go to all of them.

A complete treatment of fundamentals and recent advances in complexity theory Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form. Theory of Computational Complexity offers a thorough presentation of the fundamentals of complexity theory, including NP-completeness theory, the polynomial-time hierarchy, relativization, and the application to cryptography. It also examines the theory of nonuniform computational complexity, including the computational models of decision trees and Boolean circuits, and the notion of polynomial-time isomorphism. The theory of probabilistic complexity, which studies complexity issues related to randomized computation as well as interactive proof systems and probabilistically checkable proofs, is also covered. Extraordinary in both its breadth and depth, this volume: • Provides complete proofs of recent breakthroughs in complexity theory • Presents results in well-defined form with complete proofs and numerous exercises • Includes scores of graphs and figures to clarify difficult material An invaluable resource for researchers as well as an important guide for graduate and advanced undergraduate students, Theory of Computational Complexity is destined to become the standard reference in the field.