Computational complexity of parametric linear programming
From MaRDI portal
Publication:3887263
DOI10.1007/BF01581642zbMath0443.90102MaRDI QIDQ3887263
Publication date: 1980
Published in: Mathematical Programming (Search for Journal in Brave)
computational complexityequality constraintsexponential growthworst case analysisparametric linear programmingparametric problemspiecewise linear convex functioncost minimizing parametric right hand side linear program
Analysis of algorithms and problem complexity (68Q25) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05)
Related Items
Complexity of some parametric integer and network programming problems, Parametric problems on graphs of bounded tree-width, A new family of exponential LP problems, Fuzzy facility location-allocation problem under the Hurwicz criterion, An algorithm for approximate multiparametric convex programming, An approximation algorithm for a general class of parametric optimization problems, Criss-cross methods: A fresh view on pivot algorithms, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, Geometric algorithm for multiparametric linear programming, The inverse-parametric knapsack problem, Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint, A study of piecewise linear-quadratic programs, Facility location-allocation problem in random fuzzy environment: using \((\alpha,\beta )\)-cost minimization model under the Hurewicz criterion, Combinatorial geometries representable over GF(3) and GF(q). I: The number of points, A Friendly Smoothed Analysis of the Simplex Method, Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization, An algorithm for approximate multiparametric linear programming, Applications of the parametric programming procedure, Optimal and efficient adaptation in distributed real-time systems with discrete rates, A complexity perspective on entailment of parameterized linear constraints, Parametric maximal flows in generalized networks – complexity and algorithms, On linear multiplicative programming., Algorithms for flows with parametric capacities, A geometric view of parametric linear programming, Parametric mixed-integer 0-1 linear programming: The general case for a single parameter, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, On quantified linear implications, New results on the average behavior of simplex algorithms, A fast parametric assignment algorithm with applications in max-algebra, Graph Clustering in All Parameter Regimes, A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program, Geometry of the Gass-Saaty parametric cost LP algorithm, Fast Algorithms for Rank-1 Bimatrix Games, Zonotopes with large 2D-cuts, An efficient algorithm for the parametric resource allocation problem, Pivot rules for linear programming: A survey on recent theoretical developments, An exterior point simplex algorithm for (general) linear programming problems, The single most vital arc in the most economical path problem -- a parametric analysis, Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games, Unifying known lower bounds via geometric complexity theory
Cites Work
