Combinatorial Optimization: Theory and Algorithms

By B. Korte, J. Vygen. 2007

942 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Management Information Systems

View Paper: https://www.semanticscholar.org/paper/071188d86db5625f34722dfc38380cc045ee1688

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

In Management Information Systems

Citations in the corpus

Sparse Blossom: correcting a million errors per core second with minimum-weight matching (2023, positive): “The handling of negative edge weights was also discussed in [Hig22], as well as in Corollary 12.12 of [KV18], where what Korte and Vygen refer to as a minimum-weight T -join is equivalent to what we call a MWEM.”
Robotic load balancing for mobility-on-demand systems (2012, background): “However, it can easily be verified that the constraint matrix A is totally unimodular (Korte and Vygen, 2007).”
Downlink Radio Resource Allocation for Multi-Cell OFDMA System (2006, background): “and they are both NP-complete [ 20 ] without computational efficient algorithms to obtain the”
An improved LP-based approximation for steiner tree (2010, background): “It follows from the classical cycle rule for minimum-cost spanning tree computation that w ( F ) ≥ c ( T ) (see, e.g., Theorem 6.2 in [32]).”
A Note on Rees Algebras and the MFMC Property (2005, background): “In optimization terms [12] this means that the clutter C has the MFMC property if and only if the system of linear inequalities x ≥ 0; xA ≥ 1 that define Q(A) is totally dual integral (TDI).”
Pairwise kidney exchange (2005, neutral): “, Lovász and Plummer [31] on matchings, and Korte and Vygen [30] on matroids).”
Fitness Function in ABC Algorithm for Uncapacitated Facility Location Problem (2015, background): “The objective of the UFLP is to optimize the cost of transport to each customer and the cost associated to facility opening, when the set of potential locations of facilities and the customers are given, whereas UFLP is known to be NP-hard (see [6]).”
Quantum annealing for industry applications: introduction and review (2021, neutral): “Another way of handling constraints for the QA approach was proposed more recently [139, 197], which is very similar to Lagrangian relaxation in traditional combinatorial optimization (see, for example, [102]).”
A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing (2012, methodology): “This follows immediately by results from linear programming duality see the textbook of Korte and Vygen (2008) for more details.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “, TSP or other vehicle routing problems, are NP-hard [71], and hence likely intractable in the worst-case sense.”
Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards (2010, background): “The examples we present are far from exhausting the possible applications of the formulation and the policies we present in this work — there are many other linear-objective network optimization problems [6], [7].”