- Table View
- List View
Combinatorial Methods with Computer Applications (Discrete Mathematics and Its Applications)
by Jonathan L. GrossThis combinatorics text provides in-depth coverage of recurrences, generating functions, partitions, and permutations, along with some of the most interesting graph and network topics, design constructions, and finite geometries. It presents the computer and software algorithms in pseudo-code and incorporates definitions, theorems, proofs, examples, and nearly 300 illustrations as pedagogical elements of the exposition. Numerous problems, solutions, and hints reinforce basic skills and assist with creative problem solving. The author also offers a website with extensive graph theory informational resources as well as a computational engine to help with calculations for some of the exercises.
Combinatorial Models for Scheduling Sports Tournaments (EURO Advanced Tutorials on Operational Research)
by Celso C. Ribeiro Sebastián Urrutia Dominique de WerraThis book introduces solutions for sports scheduling problems in a variety of settings. In particular the book covers timetabling, the traveling tournament problem, carryover minimization, breaks minimization, tournament design, tournament planning, and referee assignment. A rich selection of applications to sports such as football, baseball, basketball, cricket or hockey are employed to illustrate the methods and techniques. In a step-by-step tutorial format the book describes the use of graph theory concepts, local search operators and integer programming in the context of sports scheduling. The methods presented in this book are essential to sports scheduling in all its dimensions, from tournaments that are followed by millions of people across the world, with broadcast rights that amount to hundreds of millions of dollars in some competitions, to amateur leagues that require coordination and logistical efforts due to the large number of tournaments and competitors.
Combinatorial Nullstellensatz: With Applications to Graph Colouring
by R. Balakrishnan Xuding ZhuCombinatorial Nullstellensatz is a novel theorem in algebra introduced by Noga Alon to tackle combinatorial problems in diverse areas of mathematics. This book focuses on the applications of this theorem to graph colouring. A key step in the applications of Combinatorial Nullstellensatz is to show that the coefficient of a certain monomial in the expansion of a polynomial is nonzero. The major part of the book concentrates on three methods for calculating the coefficients: Alon-Tarsi orientation: The task is to show that a graph has an orientation with given maximum out-degree and for which the number of even Eulerian sub-digraphs is different from the number of odd Eulerian sub-digraphs. In particular, this method is used to show that a graph whose edge set decomposes into a Hamilton cycle and vertex-disjoint triangles is 3-choosable, and that every planar graph has a matching whose deletion results in a 4-choosable graph. Interpolation formula for the coefficient: This method is in particular used to show that toroidal grids of even order are 3-choosable, r-edge colourable r-regular planar graphs are r-edge choosable, and complete graphs of order p+1, where p is a prime, are p-edge choosable. Coefficients as the permanents of matrices: This method is in particular used in the study of the list version of vertex-edge weighting and to show that every graph is (2,3)-choosable. It is suited as a reference book for a graduate course in mathematics.
Combinatorial Optimization Under Uncertainty: Real-Life Scenarios in Allocation Problems (Advances in Metaheuristics)
by Patrick Siarry Ritu Arora Prof. Shalini Arora Kulkarni, Dr. Anand J.This book discusses the basic ideas, underlying principles, mathematical formulations, analysis and applications of the different combinatorial problems under uncertainty and attempts to provide solutions for the same. Uncertainty influences the behaviour of the market to a great extent. Global pandemics and calamities are other factors which affect and augment unpredictability in the market. The intent of this book is to develop mathematical structures for different aspects of allocation problems depicting real life scenarios. The novel methods which are incorporated in practical scenarios under uncertain circumstances include the STAR heuristic approach, Matrix geometric method, Ranking function and Pythagorean fuzzy numbers, to name a few. Distinct problems which are considered in this book under uncertainty include scheduling, cyclic bottleneck assignment problem, bilevel transportation problem, multi-index transportation problem, retrial queuing, uncertain matrix games, optimal production evaluation of cotton in different soil and water conditions, the healthcare sector, intuitionistic fuzzy quadratic programming problem, and multi-objective optimization problem. This book may serve as a valuable reference for researchers working in the domain of optimization for solving combinatorial problems under uncertainty. The contributions of this book may further help to explore new avenues leading toward multidisciplinary research discussions.
Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16–18, 2016, Proceedings (Lecture Notes in Computer Science #10043)
by T-H. Hubert Chan Minming Li Lusheng WangThis book constitutes the refereed proceedings of the 10th International Conference on Combinatorial Optimization and Applications, COCOA 2016, held in Hong Kong, China, in December 2016. The 60 full papers included in the book were carefully reviewed and selected from 122 submissions. The papers are organized in topical sections such as graph theory, geometric optimization, complexity and data structure, combinatorial optimization, and miscellaneous.
Combinatorial Optimization and Applications: 17th International Conference, COCOA 2024, Beijing, China, December 6–8, 2024, Proceedings, Part I (Lecture Notes in Computer Science #15434)
by Dachuan Xu Donglei Du Lu HanThe two-volume set, LNCS 15434 and 15435, constitutes the refereed post-conference proceedings of the 17th International Conference on Combinatorial Optimization and Applications, COCOA 2024, held in Beijing, China, during December 6–8, 2024. The 53 full papers included in the proceedings were carefully reviewed and selected from 124 submissions. They deal with combinatorial optimization and its applications, including algorithm design, theoretical and experimental analysis, and applied research of general algorithmic interest.
Combinatorial Optimization and Applications: 17th International Conference, COCOA 2024, Beijing, China, December 6–8, 2024, Proceedings, Part II (Lecture Notes in Computer Science #15435)
by Dachuan Xu Donglei Du Lu HanThe two-volume set, LNCS 15434 and 15435, constitutes the refereed post-conference proceedings of the 17th International Conference on Combinatorial Optimization and Applications, COCOA 2024, held in Beijing, China, during December 6–8, 2024. The 53 full papers included in the proceedings were carefully reviewed and selected from 124 submissions. They deal with combinatorial optimization and its applications, including algorithm design, theoretical and experimental analysis, and applied research of general algorithmic interest.
Combinatorial Optimization and Applications: 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings (Lecture Notes in Computer Science #8881)
by Ding-Zhu Du Zhao Zhang Lidong Wu Wen XuThis 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.
Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings (Lecture Notes in Computer Science #9486)
by Ding-Zhu Du Wei Li Weili Wu Zaixin Lu Donghyun KimThis 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.
Combinatorial Optimization and Applications: A Tribute to Bernard Gendron (International Series in Operations Research & Management Science #358)
by Michel Gendreau Antonio Frangioni Teodor Gabriel CrainicCombinatorial Optimization represents a major component of Operations Research, Mathematical Programming, and, in a broader sense, the development of digital intelligence (and society). It covers, in particular, such important areas as network design, location, routing, and scheduling, with major applications in transportation, logistics, health systems, production, communications, and energy.Starting from the exceptional contribution Professor Bernard Gendron made to combinatorial optimization and its applications in multiple areas, the book presents a state-of-the-art view on the field through a combination of surveys, expository articles, and focused methodological and applied research. The authors hail from various Operations Research areas and institutions around the world. Having collaborated closely with Professor Gendron, they drew on his foundational work to showcase a variety of models and algorithms that draw a living picture of the multifaceted word of applied combinatorial optimization.
Combinatorial Optimization and Graph Algorithms: Communications of NII Shonan Meetings
by Takuro Fukunaga Ken-Ichi KawarabayashiCovering network designs, discrete convex analysis, facility location and clustering problems, matching games, and parameterized complexity, this book discusses theoretical aspects of combinatorial optimization and graph algorithms. Contributions are by renowned researchers who attended NII Shonan meetings on this essential topic. The collection contained here provides readers with the outcome of the authors' research and productive meetings on this dynamic area, ranging from computer science and mathematics to operations research. Networks are ubiquitous in today's world: the Web, online social networks, and search-and-query click logs can lead to a graph that consists of vertices and edges. Such networks are growing so fast that it is essential to design algorithms to work for these large networks. Graph algorithms comprise an area in computer science that works to design efficient algorithms for networks. Here one can work on theoretical or practical problems where implementation of an algorithm for large networks is needed. In two of the chapters, recent results in graph matching games and fixed parameter tractability are surveyed. Combinatorial optimization is an intersection of operations research and mathematics, especially discrete mathematics, which deals with new questions and new problems, attempting to find an optimum object from a finite set of objects. Most problems in combinatorial optimization are not tractable (i. e. , NP-hard). Therefore it is necessary to design an approximation algorithm for them. To tackle these problems requires the development and combination of ideas and techniques from diverse mathematical areas including complexity theory, algorithm theory, and matroids as well as graph theory, combinatorics, convex and nonlinear optimization, and discrete and convex geometry. Overall, the book presents recent progress in facility location, network design, and discrete convex analysis.
Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016, Revised Selected Papers (Lecture Notes in Computer Science #9849)
by A. Ridha Mahjoub Raffaele Cerulli Satoru FujishigeThis book constitutes the thoroughly refereed post-conference proceedings of the Second International Symposium on Combinatorial Optimization, ISCO 2012, held in Athens, Greece, in April 2012. The 37 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 94 regular and 30 short submissions. They present original research on all aspects of combinatorial optimization, ranging from mathematical foundations and theory of algorithms to computational studies and practical applications.
Combinatorial Optimization: 8th International Symposium, ISCO 2024, La Laguna, Tenerife, Spain, May 22–24, 2024, Revised Selected Papers (Lecture Notes in Computer Science #14594)
by Amitabh Basu Ali Ridha Mahjoub Juan José Salazar GonzálezThis book constitutes the refereed proceedings of the 8th International Symposium on Combinatorial Optimization, ISCO 2024, held in La Laguna, Tenerife, Spain, during May 22–24, 2024. The 30 full papers included in this book were carefully reviewed and selected from 46 submissions. They were organized in topical sections as follows: integer programming; graph theory; parameterized algorithms; approximation algorithms; integer programming for machine learning; and applications.
Combinatorial Optimization: Algorithms and Complexity (Dover Books on Computer Science)
by Christos H. Papadimitriou Kenneth SteiglitzThis clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. "Mathematicians wishing a self-contained introduction need look no further." -- American Mathematical Monthly.
Combinatorial Optimization: Networks and Matroids (Dover Books on Mathematics)
by Eugene LawlerPerceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.
Combinatorial Optimization: Theory And Algorithms (Algorithms And Combinatorics Ser. #21)
by Jens Vygen Bernhard KorteThis comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+ɛ)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.
Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R (Chapman & Hall/CRC Computational Biology Series)
by Gabriel ValienteEmphasizing the search for patterns within and between biological sequences, trees, and graphs, Combinatorial Pattern Matching Algorithms in Computational Biology Using Perl and R shows how combinatorial pattern matching algorithms can solve computational biology problems that arise in the analysis of genomic, transcriptomic, proteomic, metabolomic
Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings (Lecture Notes in Computer Science #9133)
by Ferdinando Cicalese Ely Porat Ugo VaccaroThis book constitutes the refereed proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, held on Ischia Island, Italy, in June/July 2015. The 34 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 83 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees; regular expressions; graphs; point sets; and arrays. The goal is to derive combinatorial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. The meeting also deals with problems in computational biology; data compression and data mining; coding; information retrieval; natural language processing; and pattern recognition.
Combinatorial Reasoning
by William Webb Duane DetempleWritten by well-known scholars in the field, this book introduces combinatorics alongside modern techniques, showcases the interdisciplinary aspects of the topic, and illustrates how to problem solve with a multitude of exercises throughout. The authors' approach is very reader-friendly and avoids the "scholarly tone" found in many books on this topic.Combinatorial Reasoning: An Introduction to the Art of Counting:Focuses on enumeration and combinatorial thinking as a way to develop a variety of effective approaches to solving counting problemsIncludes brief summaries of basic concepts from probability, power series, and group theory to show how combinatorics interacts with other fieldsProvides abstract ideas that are grounded in familiar concrete settings and features plentiful diagrams throughout to further add in reader understandingPresents simple and helpful notations as needed, and simple cases are treated first before more general and/or advanced casesContains over 700 exercise sets, ranging from the routine to the advanced, with either hints, short answers, or complete solutions for odd numbered problems. An Instructor's Manual (available via request to the Publisher) provides complete solutions for all exercises
Combinatorial Scientific Computing
by Uwe Naumann Olaf SchenkCombinatorial Scientific Computing explores the latest research on creating algorithms and software tools to solve key combinatorial problems on large-scale high-performance computing architectures. It includes contributions from international researchers who are pioneers in designing software and applications for high-performance computing systems
Combinatorial Search: From Algorithms To Systems
by Youssef HamadiAlthough they are believed to be unsolvable in general, tractability results suggest that some practical NP-hard problems can be efficiently solved. Combinatorial search algorithms are designed to efficiently explore the usually large solution space of these instances by reducing the search space to feasible regions and using heuristics to efficiently explore these regions. Various mathematical formalisms may be used to express and tackle combinatorial problems, among them the constraint satisfaction problem (CSP) and the propositional satisfiability problem (SAT). These algorithms, or constraint solvers, apply search space reduction through inference techniques, use activity-based heuristics to guide exploration, diversify the searches through frequent restarts, and often learn from their mistakes. In this book the author focuses on knowledge sharing in combinatorial search, the capacity to generate and exploit meaningful information, such as redundant constraints, heuristic hints, and performance measures, during search, which can dramatically improve the performance of a constraint solver. Information can be shared between multiple constraint solvers simultaneously working on the same instance, or information can help achieve good performance while solving a large set of related instances. In the first case, information sharing has to be performed at the expense of the underlying search effort, since a solver has to stop its main effort to prepare and commu nicate the information to other solvers; on the other hand, not sharing information can incur a cost for the whole system, with solvers potentially exploring unfeasible spaces discovered by other solvers. In the second case, sharing performance measures can be done with little overhead, and the goal is to be able to tune a constraint solver in relation to the characteristics of a new instance - this corresponds to the selection of the most suitable algorithm for solving a given instance. The book is suitable for researchers, practitioners, and graduate students working in the areas of optimization, search, constraints, and computational complexity.
Combinatorial Set Theory of C*-algebras (Springer Monographs in Mathematics)
by Ilijas FarahThis book explores and highlights the fertile interaction between logic and operator algebras, which in recent years has led to the resolution of several long-standing open problems on C*-algebras. The interplay between logic and operator algebras (C*-algebras, in particular) is relatively young and the author is at the forefront of this interaction. The deep level of scholarship contained in these pages is evident and opens doors to operator algebraists interested in learning about the set-theoretic methods relevant to their field, as well as to set-theorists interested in expanding their view to the non-commutative realm of operator algebras. Enough background is included from both subjects to make the book a convenient, self-contained source for students. A fair number of the exercises form an integral part of the text. They are chosen to widen and deepen the material from the corresponding chapters. Some other exercises serve as a warmup for the latter chapters.
Combinatorial Set Theory: With a Gentle Introduction to Forcing (Springer Monographs in Mathematics)
by Lorenz J. HalbeisenThis book provides a self-contained introduction to modern set theory and also opens up some more advanced areas of current research in this field. The first part offers an overview of classical set theory wherein the focus lies on the axiom of choice and Ramsey theory. In the second part, the sophisticated technique of forcing, originally developed by Paul Cohen, is explained in great detail. With this technique, one can show that certain statements, like the continuum hypothesis, are neither provable nor disprovable from the axioms of set theory. In the last part, some topics of classical set theory are revisited and further developed in the light of forcing. The notes at the end of each chapter put the results in a historical context, and the numerous related results and the extensive list of references lead the reader to the frontier of research. This book will appeal to all mathematicians interested in the foundations of mathematics, but will be of particular use to graduates in this field.
Combinatorial Set Theory: With a Gentle Introduction to Forcing (Springer Monographs in Mathematics)
by Lorenz J. HalbeisenThis book provides a self-contained introduction to modern set theory and also opens up some more advanced areas of current research in this field. The first part offers an overview of classical set theory wherein the focus lies on the axiom of choice and Ramsey theory. In the second part, the sophisticated technique of forcing, originally developed by Paul Cohen, is explained in great detail. With this technique, one can show that certain statements, like the continuum hypothesis, are neither provable nor disprovable from the axioms of set theory. In the last part, some topics of classical set theory are revisited and further developed in the light of forcing. The notes at the end of each chapter put the results in a historical context, and the numerous related results and the extensive list of references lead the reader to the frontier of research. This book will appeal to all mathematicians interested in the foundations of mathematics, but will be of particular use to graduates in this field.
Combinatorial Structures in Algebra and Geometry: NSA 26, Constanța, Romania, August 26–September 1, 2018 (Springer Proceedings in Mathematics & Statistics #331)
by Dumitru I. Stamate Tomasz SzembergThis proceedings volume presents selected, peer-reviewed contributions from the 26th National School on Algebra, which was held in Constanța, Romania, on August 26-September 1, 2018. The works cover three fields of mathematics: algebra, geometry and discrete mathematics, discussing the latest developments in the theory of monomial ideals, algebras of graphs and local positivity of line bundles. Whereas interactions between algebra and geometry go back at least to Hilbert, the ties to combinatorics are much more recent and are subject of immense interest at the forefront of contemporary mathematics research. Transplanting methods between different branches of mathematics has proved very fruitful in the past – for example, the application of fixed point theorems in topology to solving nonlinear differential equations in analysis. Similarly, combinatorial structures, e.g., Newton-Okounkov bodies, have led to significant advances in our understanding of the asymptotic properties of line bundles in geometry and multiplier ideals in algebra.This book is intended for advanced graduate students, young scientists and established researchers with an interest in the overlaps between different fields of mathematics. A volume for the 24th edition of this conference was previously published with Springer under the title "Multigraded Algebra and Applications" (ISBN 978-3-319-90493-1).