Live briefing
Everything about Combinatorial optimization
Subfield of mathematical optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Combinatorial optimizationA 5-minute orientation
- Skim a recent paper: Ising machines as hardware solvers of combinatorial optimization problemsInfluential work since 2022
- Pick up a classic book: Combinatorial theoryThe most-reprinted book on the subject
- Read the landmark paper: Metaheuristics in combinatorial optimizationCited 2,852 times
- Go sideways: Approximation algorithmA closely related topic
- Go sideways: APXA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Metaheuristics in combinatorial optimization
Metaheuristics in Combinatorial Optimization
Combinatorial optimization and Green Logistics
Direct Combinatorial Pathway Optimization
Convex Combinatorial Optimization
Generating combinatorial test suite using combinatorial optimization
Combinatorial optimization in geometry
Optimization of Combinatorial Mutagenesis
🆕 Influential since 2022
Ising machines as hardware solvers of combinatorial optimization problems
Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art
Combined DFT, SCAPS-1D, and wxAMPS frameworks for design optimization of efficient Cs 2 BiAgI 6 -based perovskite solar cells with different charge transport layers
Combinatorial optimization of mRNA structure, stability, and translation for RNA-based therapeutics
📚 Books worth reading
Combinatorial theoryHall, Marshall, Marshall Hall · 1967
Applications of Combinatorial OptimizationVangelis Th Paschos · 2010
Combinatorial OptimizationBernhard Korte, Jens Vygen · 2005
Concepts of Combinatorial OptimizationVangelis Th Paschos · 2012
Graphs, Networks and AlgorithmsDieter Jungnickel · 2006
Integer and combinatorial optimizationGeorge L. Nemhauser · 1988
Combinatorial optimizationChristos H. Papadimitriou · 1981- 📕Probabilistic Combinatorial Optimization on GraphsCécile Murat, Vangelis Th Paschos · 2006
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems…
- APX In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time…
- Optimization problem In mathematics, engineering, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions…
- Travelling salesman problem In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances…
- Submodular set function In mathematics, a submodular set function (also known as a submodular function) is a set function that, informally, describes the relationship between…
- Greedy algorithm A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices. Greedy…
- Maximum satisfiability problem In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given…
- Bottleneck traveling salesman problem The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian…