Theory of linear and integer programming

By Alexander Schrijver. 1986

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

The Price of Fair PCA: One Extra Dimension (2018, neutral): “5 log(1 /(cid:15) )) [Schrijver, 1998] time, respectively.”
Selected Topics in Column Generation (2002, background): “Consider a linear program (the original or compact formulation ) x (cid:1) 0 (7) It is well known (Schrijver 1986) that we can write each x ∈ P as a convex combination of extreme points (cid:11) p q q ∈ Q plus a nonnegative combination of extreme rays (cid:11) p r r ∈ R of P , i.e., where the index…”
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, unknown): “A corollary of the proof is this: Corollary 4 For every n there is a 4-player game, Γ n , of size O ( n ) , with an (cid:2) -NE, x (cid:2) , where (cid:2) = 1 / 2 2 Ω( n ) , such that x (cid:2) has l ∞ -distance 1 from every actual NE.”
An Optimal Deadlock Prevention Policy for Flexible Manufacturing Systems Using Petri Net Models with Resources and the Theory of Regions (2002, methodology): “The algorithm of von zur Gathen and Sieveking (see [ 37 ]), given MA as input, produces in time polynomial in m − n + 1 and p (or S = n and E = p, because m n p, follows from determinism of A) a basis {1, 2, %, k} for Ker(MA) = Rabs(A).”
Efficient encoding of low-density parity-check codes (2001, unknown): “programming, [19].”
Maximum Likelihood Estimation in Log-Linear Models: Theory and Algorithms (2011, background): “al. Note also that isomorphic faces of the polyhedra have the same dimension. Therefore, it is sufﬁcient to prove the claim for TV instead of CV. Using the H-representation (see, e.g., Ziegler, 1998; Schrijver, 1998) we write, CA t t P Rd: Ct ¤ 0 u (41) for some matrix C, where we can assume that n”
Using linear programming to Decode Binary linear codes (2005, methodology): “In the following, we use the fact that all optimum points of a linear program with rational coefficients are themselves rational [23].”
Mixed-integer quadratic programming is in NP (2014, background): “(See [16] for more details.)”
Nonlinear Discrete Optimization (2010, methodology): “In integer programming, with S = {x ∈ Z : Ax ≤ b} given by inequalities, mostly in standard form S = {x ∈ Z : Ax = b, l ≤ x ≤ u}, the binary length of ρ(S) is polynomially bounded in the binary length 〈A, b, l, u〉 of the data by Cramer’s rule, see, for example [90].”
Mixed-integer nonlinear optimization*† (2013, unknown): “1 of Schrijver (1986). 2”
Minimal Controllability Problems (2013, background): “can be done in polynomial time in m, p [31].”
A Geometric Theory for Hypergraph Matching (2011, background): “This question was further studied by Szymańska [53], who proved that for δ < 1/k the problem PM(k, 0) admits a polynomial-time reduction to PM(k, δ), and so PM(k, δ) is NP-complete for such δ.”
A survey of computational complexity results in systems and control (2000, methodology): “It can be veri"ed (see, e.g., Schrijver, 1986) that Gaussian elimination can be implemented with O(n) arithmetic operations and so that every intermediate quantity produced is an integer of magnitude O((n;)”
Convex Models of Distribution System Reconfiguration (2012, background): “Continuous QPs have polyhedral feasible sets, and thus their mixed-integer counterparts enjoy fast algorithms similar to those for mixed-integer linear programming, namely cutting planes coupled with branch-and-bound [20].”