Combinatorial optimization. Polyhedra and efficiency.

By Alexander Schrijver. 2003

3,897 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/f9e591692d6aab0e1cf0c1ea4948597195657edf

How researchers see this paper

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

Citations in the corpus

Graphical Models, Exponential Families, and Variational Inference (2008, background): “This maximum weight matching (MWM) problem is well known to be solvable in polynomial time for any graph [207].”
A genetic algorithm approach to developing the multi-echelon reverse logistics network for product returns (2006, unknown): “, [20] for a definition of NP-completeness).”
Combinatorial algebra : syntax and semantics (2014, unknown): “This lemma is one of the most important statements in combinatorics and has numerous applications in many areas of mathematics (see [273, 287, 9]).”
Hidden Part Models for Human Action Recognition: Probabilistic versus Max Margin (2011, methodology): “The inference of this structure can be solved by MMHCRFs using LP [29], [49].”
Mixed Integer Linear Programming Formulation Techniques (2015, methodology): “An important part of LP or polyhedral methods for combinatorial optimization can be interpreted as the construction of sharp or locally ideal formulations for such problems [146].”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, unknown): “We refer the reader [31] for a detailed introduction to basic matroid theory.”
A Combinatorial Approach to Nonlocality and Contextuality (2012, background): “Now it is known [86] that the polytope of all matchings on Cn is given by”
Distributionally Robust Convex Optimization (2014, background): “We assume that the ambiguity set P in (3) is representable in the standard form P = P ∈ P0(RP × RQ) : EP [Az̃ +Bũ] = b,P [(z̃, ũ) ∈ Ci] ∈ [pi,pi] ∀i ∈ I , (4) where P represents a joint probability distribution of the random vector z̃ ∈ RP appearing in the constraint function v in (3) and some…”
A Discriminative Matching Approach to Word Alignment (2005, background): “This LP is guaranteed to have integral (and hence optimal) solutions for any scoring function s(y) (Schrijver, 2003).”
Maximum matchings via Gaussian elimination (2004, background): “(1)Schrijver suggests in [15], that this paper shows how to actually construct the matching, but this is not true.”
Submodular maximization by simulated annealing (2010, methodology): “We use a basic property of matroids (see [29]) which says that for any two independent sets C, I ∈ I, there is a mapping m : C \ I → (I \ C) ∪ {0} such that for each i ∈ C \ I, I −m(i) + i is independent, and each element of I \C appears at most once as m(i).”
Approximating the stochastic knapsack problem: the benefit of adaptivity (2004, background): “In general, the function ggJ tt can be obtained as ggJ tt = min A⊆J tf A + J \AAA (see Schrijver [21]).”
Structured Prediction via the Extragradient Method (2005, background): “As in the min-cut problem, this LP is guaranteed to have integral solutions for any scoring function s(y) [17].”
FemtoCaching: Wireless video content delivery through distributed caching helpers (2011, background): “Xbh is the boolean representation of Xh = X∩Sh and X̄bh is the complement of Xbh.”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, methodology): “These special classes include graphical models with tree-structured dependencies, models with submodular potential functions, models encoding bipartite matching problems, and those with nand potentials and perfect graph structures (Wainwright and Jordan, 2008; Schrijver, 2003; Jebara, 2009; Foulds e”