Computational complexity of parametric linear programming
DOI10.1007/BF01581642zbMATH Open0443.90102MaRDI QIDQ3887263FDOQ3887263
Authors: Katta G. Murty 
Publication date: 1980
Published in: Mathematical Programming (Search for Journal in Brave)
computational complexityworst case analysisexponential growthequality constraintsparametric linear programmingparametric problemspiecewise linear convex functioncost minimizing parametric right hand side linear program
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Sensitivity, stability, parametric optimization (90C31)
Cites Work
Cited In (43)
- An efficient algorithm for the parametric resource allocation problem
- Complexity of some parametric integer and network programming problems
- An algorithm for approximate multiparametric linear programming
- The inverse-parametric knapsack problem
- A new family of exponential LP problems
- A friendly smoothed analysis of the simplex method
- Parametric maximal flows in generalized networks – complexity and algorithms
- Criss-cross methods: A fresh view on pivot algorithms
- On quantified linear implications
- Fast Algorithms for Rank-1 Bimatrix Games
- Parametric computation of minimum-cost flows with piecewise quadratic costs
- New results on the average behavior of simplex algorithms
- Algorithms for flows with parametric capacities
- Graph Clustering in All Parameter Regimes
- Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games
- Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
- Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization
- Zonotopes with large 2D-cuts
- Unifying known lower bounds via geometric complexity theory
- On linear multiplicative programming.
- Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
- A study of piecewise linear-quadratic programs
- The single most vital arc in the most economical path problem -- a parametric analysis
- A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program
- Parametric problems on graphs of bounded tree-width
- Pivot rules for linear programming: A survey on recent theoretical developments
- A novel parallel combinatorial algorithm for multiparametric programming
- Applications of the parametric programming procedure
- Facility location-allocation problem in random fuzzy environment: using \((\alpha,\beta )\)-cost minimization model under the Hurewicz criterion
- A geometric view of parametric linear programming
- Optimal and efficient adaptation in distributed real-time systems with discrete rates
- A complexity perspective on entailment of parameterized linear constraints
- Combinatorial geometries representable over GF(3) and GF(q). I: The number of points
- Unifying lower bounds for algebraic machines, semantically
- An approximation algorithm for a general class of parametric optimization problems
- Upper and lower bounds on the smoothed complexity of the simplex method
- A fast parametric assignment algorithm with applications in max-algebra
- Fuzzy facility location-allocation problem under the Hurwicz criterion
- Geometric algorithm for multiparametric linear programming
- Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
- An exterior point simplex algorithm for (general) linear programming problems
- An algorithm for approximate multiparametric convex programming
- Geometry of the Gass-Saaty parametric cost LP algorithm
This page was built for publication: Computational complexity of parametric linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3887263)
