scientific article

Publication date: 1979

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity vector optimization polynomial algorithm simplex method polynomial solvability complex linear programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05)

Related Items (only showing first 100 items - show all)

A 71/60 theorem for bin packing ⋮ Homotopy techniques in linear programming ⋮ Karmarkar's algorithm and the ellipsoid method ⋮ KBO orientability ⋮ Computing a quasi-perfect equilibrium of a two-player game ⋮ Computing equilibria: a computational complexity perspective ⋮ Scheduling jobs with fixed start and end times ⋮ A multiplicative barrier function method for linear programming ⋮ Single-projection procedure for linear optimization ⋮ Probabilistic satisfiability ⋮ Binary classification posed as a quadratically constrained quadratic programming and solved using particle swarm optimization ⋮ New trends in machine scheduling ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ A relaxed version of Karmarkar's method ⋮ A polynomial-time algorithm, based on Newton's method, for linear programming ⋮ The complexity of recognizing polyhedral scenes ⋮ Eliminating columns in the simplex method for linear programming ⋮ Minimal ellipsoids and their duals ⋮ An extension of Karmarkar's projective algorithm for convex quadratic programming ⋮ The Boolean quadratic polytope: Some characteristics, facets and relatives ⋮ Subspaces with well-scaled frames ⋮ A polynomial-time algorithm for a class of linear complementarity problems ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant ⋮ A brief history of the international symposia on mathematical programming ⋮ A note on Khatchian's algorithm ⋮ On the complexity of quantified linear systems ⋮ An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ \((k,j)\)-coloring of sparse graphs ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ Coping with selfish on-going behaviors ⋮ Selectivity in probabilistic causality: where psychology runs into quantum physics ⋮ Positive diagonal scaling of a nonnegative tensor to one with prescribed slice sums ⋮ Multiobjective network scheduling with efficient use of renewable and nonrenewable resources ⋮ Two complexity results on \(c\)-optimality in experimental design ⋮ Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient ⋮ Interior point methods 25 years later ⋮ A ``build-down scheme for linear programming ⋮ Sequential virtual motion camouflage method for nonlinear constrained optimal trajectory control ⋮ A counterexample to the Hirsch conjecture ⋮ An algorithm for linear programming that is easy to implement ⋮ Is binary encoding appropriate for the problem-language relationship? ⋮ On the combinatorial problems which I would most like to see solved ⋮ The ellipsoid method and its consequences in combinatorial optimization ⋮ Solving linear programs from sign patterns ⋮ An appraisal of computational complexity for operations researchers ⋮ Complexity of computations in Commutative Division of the USSR Academy of Sciences ⋮ A class of linear complementarity problems solvable in polynomial time ⋮ On the complexity of generalized due date scheduling problems ⋮ Correlation polytopes: Their geometry and complexity ⋮ Simple search methods for finding a Nash equilibrium ⋮ Semidefinite programming for min-max problems and games ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ An analytical comparison of different formulations of the travelling salesman problem ⋮ A complexity perspective on entailment of parameterized linear constraints ⋮ Temporal constraint networks ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ The complexity of optimizing over a simplex, hypercube or sphere: a short survey ⋮ A simpler and tighter redundant Klee-Minty construction ⋮ On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals ⋮ A canonical form for generalized linear constraints ⋮ Learning in parallel ⋮ The complexity of stochastic games ⋮ George B. Dantzig and systems optimization ⋮ George Dantzig's impact on the theory of computation ⋮ Analyzing restricted fragments of the theory of linear arithmetic ⋮ The double pivot simplex method ⋮ Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices ⋮ A combinatorial certifying algorithm for linear feasibility in UTVPI constraints ⋮ Sparse approximate solution of partial differential equations ⋮ A strongly polynomial algorithm for linear systems having a binary solution ⋮ Scheduling ordered open shops ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ Open problems in computational linear algebra ⋮ A redundant Klee-Minty construction with all the redundant constraints touching the feasible region ⋮ Approximated consistency for the automatic recording constraint ⋮ A polynomial projection algorithm for linear feasibility problems ⋮ Multiline addressing by network flow ⋮ The \(C^m\) norm of a function with prescribed jets. II ⋮ Interactive multiple objective optimization: Survey. I: Continuous case ⋮ Multicommodity flows in certain planar directed networks ⋮ A new polynomial-time algorithm for linear programming ⋮ Variations on a theme by Akl and Taylor: security and tradeoffs ⋮ Scl in graphs of groups ⋮ Linear programming under randomness and fuzziness ⋮ Preemptive scheduling of independent jobs on parallel machines subject to financial constraints ⋮ The vertices of the knapsack polytope ⋮ Threshold hypergraphs ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ The complexity of facets (and some facets of complexity) ⋮ Solving systems of polynomial inequalities over a real closed field in subexponential time ⋮ Interior-point algorithms for global optimization ⋮ A quadratically convergent method for linear programming ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ Intelligent gradient search in linear programming ⋮ Updating beliefs with incomplete observations ⋮ Small solutions of linear diophantine equations ⋮ Generation of interior points and polyhedral representations of cones in \(\mathbb R^N\) cut by \(M\) planes sharing a common point

This page was built for publication: