%{search_type} search results

• 1. Introduction.
• -2. Divide-and-Conquer.-
• 3. Dynamic Programming and Shortest Path.-
• 4. Greedy Algorithm and Spanning Tree.-
• 5. Incremental Method and Maximum Network Flow.-
• 6. Linear Programming.-
• 7. Primal-Dual Methods and Minimum Cost Flow.-
• 8. NP-hard Problems and Approximation Algorithms.-
• 9. Restriction and Steiner Tree.-
• 10. Greedy Approximation and Submodular Optimization.-
• 11. Relaxation and Rounding.
• 12. Nonsubmodular Optimization.- Bibliography.
• (source: Nielsen Book Data)

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.
(source: Nielsen Book Data)

• SOC Functions.- SOC-convexity and SOC-Monotonity.- Algorithmic Applications.- SOC Means and SOC Inequalities.- Possible Extensions.
• (source: Nielsen Book Data)

This book covers all of the concepts required to tackle second-order cone programs (SOCPs), in order to provide the reader a complete picture of SOC functions and their applications. SOCPs have attracted considerable attention, due to their wide range of applications in engineering, data science, and finance. To deal with this special group of optimization problems involving second-order cones (SOCs), we most often need to employ the following crucial concepts: (i) spectral decomposition associated with SOCs, (ii) analysis of SOC functions, and (iii) SOC-convexity and -monotonicity. Moreover, we can roughly classify the related algorithms into two categories. One category includes traditional algorithms that do not use complementarity functions. Here, SOC-convexity and SOC-monotonicity play a key role. In contrast, complementarity functions are employed for the other category. In this context, complementarity functions are closely related to SOC functions; consequently, the analysis of SOC functions can help with these algorithms.
(source: Nielsen Book Data)

• 1 Introduction.- 2 Graphs.- 3 Linear Programming.- 4 Linear Programming Algorithms.- 5 Integer Programming.- 6 Spanning Trees and Arborescences.- 7 Shortest Paths.- 8 Network Flows.- 9 Minimum Cost Flows.- 10 Maximum Matchings.- 11 Weighted Matching.- 12 b-Matchings and T -Joins.- 13 Matroids.- 14 Generalizations of Matroids.- 15 NP-Completeness.- 16 Approximation Algorithms.- 17 The Knapsack Problem.- 18 Bin-Packing.- 19 Multicommodity Flows and Edge-Disjoint Paths.- 20 Network Design Problems.- 21 The Traveling Salesman Problem.- 22 Facility Location.- Indices.
• (source: Nielsen Book Data)

This 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+e)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.
(source: Nielsen Book Data)

• Preface xiii Chapter 1. Airline Crew Pairing Optimization 1 Laurent ALFANDARI and Anass NAGIH 1.1. Introduction 1 1.2. Definition of the problem 2 1.3. Solution approaches 7 1.4. Solving the subproblem for column generation 11 1.5. Conclusion 21 1.6. Bibliography 22 Chapter 2. The Task Allocation Problem 23 Moaiz BEN DHAOU and Didier FAYARD 2.1. Presentation 24 2.2. Definitions and modeling 24 2.3. Review of the main works 29 2.4. A little-studied model 38 2.5. Conclusion 43 2.6. Bibliography 43 Chapter 3. A Comparison of Some Valid Inequality GenerationMethods for General 0 1 Problems 49 Pierre BONAMI and Michel MINOUX 3.1. Introduction 49 3.2. Presentation of the various techniques tested 53 3.3. Computational results 67 3.4. Bibliography 70 Chapter 4. Production Planning 73 Nadia BRAUNER, Gerd FINKE and Maurice QUEYRANNE 4.1. Introduction 73 4.2. Hierarchical planning 74 4.3. Strategic planning and productive system design 75 4.4. Tactical planning and inventory management 77 4.5. Operations planning and scheduling 90 4.6. Conclusion and perspectives 104 4.7. Bibliography 105 Chapter 5. Operations Research and Goods Transportation111 Teodor Gabriel CRAINIC and Frederic SEMET 5.1. Introduction 111 5.2. Goods transport systems 113 5.3. Systems design 115 5.4. Long-distance transport 122 5.5. Vehicle routing problems 137 5.6. Exact models and methods for the VRP 139 5.7. Heuristic methods for the VRP 147 5.8. Conclusion 160 5.9. Appendix: metaheuristics 161 5.10. Bibliography 164 Chapter 6. Optimization Models for Transportation SystemsPlanning 177 Teodor Gabriel CRAINIC and Michael FLORIAN 6.1. Introduction 177 6.2. Spatial interaction models 178 6.3. Traffic assignment models and methods 181 6.4. Transit route choice models 193 6.5. Strategic planning of multimodal systems 197 6.6. Conclusion 204 6.7. Bibliography 204 Chapter 7. A Model for the Design of a Minimum-costTelecommunications Network 209 Marc DEMANGE, Cecile MURAT, Vangelis Th. PASCHOS and SophieTOULOUSE 7.1. Introduction 209 7.2. Minimum cost network construction 210 7.3. Mathematical model, general context 213 7.4. Proposed algorithm 216 7.5. Critical points 220 7.6. Conclusion 223 7.7. Bibliography 223 Chapter 8. Parallel Combinatorial Optimization 225 Van-Dat CUNG, Bertrand LE CUN and Catherine ROUCAIROL 8.1. Impact of parallelism in combinatorial optimization 225 8.2. Parallel metaheuristics 226 8.3. Parallelizing tree exploration in exact methods 235 8.4. Conclusion 247 8.5. Bibliography 248 Chapter 9. Network Design Problems: Fundamental Methods253 Alain Quilliot 9.1. Introduction 253 9.2. The main mathematical and algorithmic tools for networkdesign 258 9.3. Models and problems 275 9.4. The STEINER-EXTENDED problem 280 9.5. Conclusion 281 9.6 Bibliography 281 Chapter 10. Network Design Problems: Models and Applications291 Alain Quilliot 10.1. Introduction 291 10.2. Models and location problems 293 10.3. Routing models for telecommunications 298 10.4. The design or dimensioning problem in telecommunications301 10.5. Coupled flows and multiflows for transport and production306 10.6. A mixed network pricing model 314 10.7. Conclusion 319 10.8. Bibliography 319 Chapter 11. Multicriteria Task Allocation to HeterogenousProcessors with Capacity and Mutual Exclusion Constraints327 Bernard ROY and Roman SLOWINSKI 11.1. Introduction and formulation of the problem 328 11.2. Modeling the set of feasible assignments 331 11.3. The concept of a blocking configuration and analysis ofthe unblocking means 334 11.4. The multicriteria assignment problem 346 11.5. Exploring a set of feasible non-dominated assignments inthe plane g2 &times
• g3 348 11.6. Numerical example 357 11.7. Conclusion 363 11.8. Bibliography 364 List of Authors 365 Index 369 Summary of Other Volumes in the Series 373.
• (source: Nielsen Book Data)

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains:mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aimsto cover a wide range of topics in this area. These topics alsodeal with fundamental notions and approaches as with severalclassical applications of combinatorial optimization. Applications of Combinatorial Optimization ispresenting a certain number among the most common and well-knownapplications of Combinatorial Optimization.
(source: Nielsen Book Data)

• 1 Introduction.- 2 Graphs.- 3 Linear Programming.- 4 Linear Programming Algorithms.- 5 Integer Programming.- 6 Spanning Trees and Arborescences.- 7 Shortest Paths.- 8 Network Flows.- 9 Minimum Cost Flows.- 10 Maximum Matchings.- 11 Weighted Matching.- 12 b-Matchings and T -Joins.- 13 Matroids.- 14 Generalizations of Matroids.- 15 NP-Completeness.- 16 Approximation Algorithms.- 17 The Knapsack Problem.- 18 Bin-Packing.- 19 Multicommodity Flows and Edge-Disjoint Paths.- 20 Network Design Problems.- 21 The Traveling Salesman Problem.- 22 Facility Location.- Indices.
• (source: Nielsen Book Data)

This 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 fifth edition has again been updated, revised, and significantly extended, with more than 60 new exercises and new material on various topics, including Cayley's formula, blocking flows, faster b-matching separation, multidimensional knapsack, multicommodity max-flow min-cut ratio, and sparsest cut. Thus, this book represents the state of the art of combinatorial optimization.
(source: Nielsen Book Data)

"This book presents recent developments and new trends in Combinatorial Optimization. Combinatorial Optimization is an active research area that has applications in many domains such as communications, network design, VLSI, scheduling, production, computational biology. In the past years, new results and major advances have been seen in many areas including computational complexity, approximation algorithms, cutting-plane based methods and submodularity function minimization. More efficient and powerful methods have been developed for approaching real-worlds problems, and new concepts and theoritical results have been introduced"-- Provided by publisher.

This comprehensive textbook on combinatorial optimization puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. Since the complete book contains enough material for at least four semesters (4 hours a week), one usually selects material in a suitable way. The book contains complete but concise proofs, also for many deep results, some of which did not appear in a book before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state of the art of combinatorial optimization.This third edition contains a new chapter on facility location problems, an area which has been extremely active in the past few years. Furthermore there are several new sections and further material on various topics. New exercises and updates in the bibliography were added. From the reviews of the 2nd edition: 'This book on combinatorial optimization is a beautiful example of the ideal textbook' - Operations Research Letters 33 (2005), p.216-217. 'The second edition (with corrections and many updates) of this very recommendable book documents the relevant knowledge on combinatorial optimization and records those problems and algorithms that define this discipline today. To read this is very stimulating for all the researchers, practitioners, and students interested in combinatorial optimization' - OR News 19 (2003), p.42.
(source: Nielsen Book Data)

• Introduction
• Polytopes and linear programming
• 1. Matroids and the greedy algorithm
• 2. Minimum-weight dipaths
• 3. Matroid intersection
• 4. Matching
• 5. Flows and cuts
• 6. Cutting planes
• 7. Branch-&-bound
• 8. Optimizing submodular functions
• Appendix.
• (source: Nielsen Book Data)

A First Course in Combinatorial Optimization is a text for a one-semester introductory graduate-level course for students of operations research, mathematics, and computer science. It is a self-contained treatment of the subject, requiring only some mathematical maturity. Topics include: linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. Central to the exposition is the polyhedral viewpoint, which is the key principle underlying the successful integer-programming approach to combinatorial-optimization problems. Another key unifying topic is matroids. The author does not dwell on data structures and implementation details, preferring to focus on the key mathematical ideas that lead to useful models and algorithms. Problems and exercises are included throughout as well as references for further study.
(source: Nielsen Book Data)

• v. A. Paths, flows, matchings chapters 1-38
• v. B. Matroids, trees, stable sets chapters 39-69
• v. C. Disjoint paths, hypergraphs chapters 70-83.

This book offers an in-depth overview of polyhedral methods and efficient algorithms in combinatorial optimization. These methods form a broad, coherent and powerful kernel in combinatorial optimization, with strong links to discrete mathematics, mathematical programming and computer science. In eight parts, various areas are treated, each starting with an elementary introduction to the area, with short, elegant proofs of the principal results, and each evolving to the more advanced methods and results, with full proofs of some of the deepest theorems in the area. Over 4000 references to further research are given, and historical surveys on the basic subjects are presented.
(source: Nielsen Book Data)

• Preface * Introduction * Graphs * Linear Programming * Linear Programming Algorithms * Integer Programming * Spanning Trees and Arborescences * Shortest Paths * Network Flows * Minimum cost Flows * Maximum Matchings * Weighted Matching * b-Matchings and T-Joins * Matroids * Generalizations of Matroids * NP-Completeness * Approximation Algorithms * The Knapsack Problem * Bin Packing * Multicommodity Flows and Edge-Disjoint Paths * Network Design Problems * The Traveling Salesman Problem * Notation Index * Author Index * Subject Index.
• (source: Nielsen Book Data)

This comprehensive textbook on combinatorial optimization puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics.It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. Since the complete book contains enough material for at least four semesters (4 hours a week), one usually selects material in a suitable way.The book contains complete (but concise) proofs, also for many deep results, some of which did not appear in a book before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state of the art of combinatorial optimization.From the reviews of the 2nd edition:"This book on combinatorial optimization is a beautiful example of the ideal textbook. [...] The second edition (with corrections and many updates) of this very recommendable book documents the relevant knowledge on combinatorial optimization and records those problems and algorithms that define this discipline today. To read this is very stimulating for all the researchers, practitioners, and students interested in combinatorial optimization." J. Kohler, Halle an der SaaleELSEVIER Operations Rearch Letters, 2005, Issue 33.
(source: Nielsen Book Data)

• Preface.- Introduction.- Graphs.- Linear Programming.- Linear Programming Algorithms.- Integer Programming.- Spanning Trees and Arborescences.- Shortest Paths.- Network Flows.- Minimum cost Flows.- Maximum Matchings.- Weighted Matching.- b-Matchings and T-Joins.- Matroids.- Generalizations of Matroids.- NP-Completeness.- Approximation Algorithms.- The Knapsack Problem.- Bin Packing.- Multicommodity Flows and Edge-Disjoint Paths.- Network Design Problems.- The Traveling Salesman Problem.- Notation Index.- Author Index.- Subject Index.
• (source: Nielsen Book Data)

This comprehensive textbook on combinatorial optimization puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. Since the complete book contains enough material for at least four semesters (4 hours a week), one usually selects material in a suitable way. The book contains complete (but concise) proofs, also for many deep results, some of which did not appear in a book before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state-of-the-art of combinatorial optimization.
(source: Nielsen Book Data)

• Preface - Data Correcting Algorithms in Combinatorial Optimization - The Steiner Ratio of Banach-Minkowski Space - Probabilistic Verification and Non-Approximability - Steiner Trees in Industry - Network-Based Model and Algorithms in Data Mining and Knowledge Discovery - The Generalized Assignment Problem and Extensions - Optimal Rectangular Partitions - Connected Dominating Sets in Sensor Networks and MANETs - Author Index - Subject Index.
• (source: Nielsen Book Data)

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.
(source: Nielsen Book Data)

• Problems and Algorithms
• Optimal Trees and Paths
• Maximum Flow Problems
• Minimum-Cost Flow Problems
• Optimal Matchings
• Integrality of Polyhedra
• The Traveling Salesman Problem
• Matroids
• NP and NP-Completeness
• Appendix
• Bibliography
• Index.
• (source: Nielsen Book Data)

A complete, highly accessible introduction to one of today's most exciting areas of applied mathematics One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade. Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include:Network flow problemsOptimal matchingIntegrality of polyhedraMatroidsNP-completenessFeaturing logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come.
(source: Nielsen Book Data)

• Polyhedra and Algorithms.- New classes of facets for complementarity knapsack problems.- Branch-and-Cut for a 2-Commodity Flow Relocation Model with Time Constraints.- The Constrained-Routing and Spectrum Assignment Problem: Valid Inequalities and Branch-and-Cut Algorithm.- Polyhedra and Combinatorics.- Top-$k$ List Aggregation: Mathematical Formulations and Polyhedral Comparisons.- Bounded variation in binary sequences.- On Minimally Non-Firm Binary Matrices.- Few Induced Disjoint Paths for H-Free Graphs.- On Permuting some Coordinates of Polytopes.- Non-linear Optimization.- Piecewise linearization of bivariate nonlinear functions: minimizing the number of pieces under a bounded approximation error.- An outer-approximation algorithm for maximum-entropy sampling.- Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear Optimization.- Game Theory.- Exact Price of Anarchy for Weighted Congestion Games with Two Players.- Nash balanced assignment problem.- Graphs and Trees.- On the thinness of trees.- Generating Spanning Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms.- Cutting and Packing.- High Multiplicity Strip Packing with Three Rectangle Types.- Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions.- Applications.- One transfer per patient suffices: Structural insights about patient-to-room assignment.- Tool switching problems in the context of overlay printing with multiple colours.- Optimal Vaccination Strategies for Multiple Dose Vaccinations.- Approximation Algorithms.- Pervasive Domination.- Unified Greedy Approximability Beyond Submodular Maximization.- Neighborhood persistency of the linear optimization relaxation of integer linear optimization.- Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines.
• (source: Nielsen Book Data)

This book constitutes thoroughly refereed and revised selected papers from the 7th International Symposium on Combinatorial Optimization, ISCO 2022, which was held online during May 18-20, 2022. The 24 full papers included in this book were carefully reviewed and selected from 50 submissions. They were organized in topical sections as follows: Polyhedra and algorithms; polyhedra and combinatorics; non-linear optimization; game theory; graphs and trees; cutting and packing; applications; and approximation algorithms.
(source: Nielsen Book Data)