Publication:3050157

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90C31: Sensitivity, stability, parametric optimization

90C05: Linear programming

Related Items

Scheduling ordered open shops, Graph theory (algorithmic, algebraic, and metric problems), Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, Interactive multiple objective optimization: Survey. I: Continuous case, Multicommodity flows in certain planar directed networks, A new polynomial-time algorithm for linear programming, Preemptive scheduling of independent jobs on parallel machines subject to financial constraints, 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, Updating beliefs with incomplete observations, Fixed interval scheduling: models, applications, computational complexity and algorithms, A ``build-down scheme for linear programming, An algorithm for linear programming that is easy to implement, Solving linear programs from sign patterns, Simple search methods for finding a Nash equilibrium, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, A simpler and tighter redundant Klee-Minty construction, George B. Dantzig and systems optimization, George Dantzig's impact on the theory of computation, 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, Linear programming under randomness and fuzziness, The vertices of the knapsack polytope, Threshold hypergraphs, Combinatorial analysis (nonnegative matrices, algorithmic problems), The complexity of facets (and some facets of complexity), Intelligent gradient search in linear programming, Small solutions of linear diophantine equations, A 71/60 theorem for bin packing, Homotopy techniques in linear programming, Karmarkar's algorithm and the ellipsoid method, Scheduling jobs with fixed start and end times, A multiplicative barrier function method for linear programming, Probabilistic satisfiability, New trends in machine scheduling, 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, The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant, A note on Khatchian's algorithm, Multiobjective network scheduling with efficient use of renewable and nonrenewable resources, 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, 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, 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, Temporal constraint networks, The complexity of problems involving structurally bounded and conservative Petri nets, 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, On the computational behavior of a polynomial-time network flow algorithm, On a graph partition problem with application to VLSI layout, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, Approximation algorithms for geometric median problems, On max-flow min-cut and integral flow properties for multicommodity flows in directed networks, A unifying approach to temporal constraint reasoning, Single machine scheduling subject to deadlines and resource dependent processing times, Main directions in the development of informatics, A semantical framework for supporting subjective and conditional probabilities in deductive databases, A deep cut ellipsoid algorithm for convex programming: Theory and applications, Asymptotic analysis of the exponential penalty trajectory in linear programming, A theory for memory-based learning, Polynomial algorithms for linear programming over the algebraic numbers, A branch bound method for subset sum problem, On the complexity of some basic problems in computational convexity. I. Containment problems, A primal-dual interior point method whose running time depends only on the constraint matrix, Solving linear programming problems exactly, Linear programming, the simplex algorithm and simple polytopes, Interior-point methods: An old and new approach to nonlinear programming, On properties of unit interval graphs with a perceptual motivation, A potential reduction approach to the frequency assignment problem, Some thoughts on combinatorial optimisation, Optimal deviations from an asset allocation., Specialized fast algorithms for IQC feasibility and optimization problems., \(O(n^ 3)\) noniterative heuristic algorithm for linear programs with error-free implementation., Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, Symbiosis between linear algebra and optimization, Academician V. S. Mikhalevich as a scientist and science organizer (on the occasion of his 70th birthday), The asymptotic optimal partition and extensions of the nonsubstitution theorem, Using selective orthonormalization to update the analytic center after addition of multiple cuts, The gap between monotone and non-monotone circuit complexity is exponential, Containing and shrinking ellipsoids in the path-following algorithm, Deriving Karmarkar's LP algorithm using angular projection matrix, Fast finite methods for a system of linear inequalities, Regular triangulations and Steiner points, Complexity aspects of a semi-infinite optimization problem†, A simple polynomial-time rescaling algorithm for solving linear programs, Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning, Generating all vertices of a polyhedron is hard, A general lower bound on the number of examples needed for learning, Probabilistic game automata, Review of properties of different precedence graphs for scheduling problems, Analytic centers and repelling inequalities, Some aspects of studying an optimization or decision problem in different computational models, Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization, A practical implementation of stochastic programming: an application to the evaluation of option contracts in supply chains, Bounded self-stabilizing Petri nets, Optimization of computations, Identifying an optimal basis in linear programming, Some directions and results of research in mathematical programming and system analysis, A unifying geometric solution framework and complexity analysis for variational inequalities, On the solution set of a linear equation with the right-hand side and operator given by intervals, A cutting plane algorithm for convex programming that uses analytic centers, Linear programming, complexity theory and elementary functional analysis, On complexity of matrix scaling, A direct heuristic algorithm for linear programming, On PAC learning algorithms for rich Boolean function classes, Algorithms for bivariate zonoid depth, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, Modified Fourier's method of solving linear programming problems., How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, An optimal randomized algorithm for \(d\)-variate zonoid depth, A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs, Optimal preemptive scheduling on a fixed number of identical parallel machines, Improved complexity results on solving real-number linear feasibility problems, On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, A Class of Balanced Matrices Arising from Location Problems, A class of rank-two ellipsoid algorithms for convex programming, Application of the ellipsoid method in an interactive procedure for multicriteria linear programming, Some recognition problems related to graph isomorphism, Resolution Width and Cutting Plane Rank Are Incomparable, Khachiyan's Algorithmus, Method of ellipsoids, its generalizations and applications, Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games, The polynomial hierarchy and a simple model for competitive analysis, On box totally dual integral polyhedra, A Variable-Complexity Norm Maximization Problem, A class of convergent primal-dual subgradient algorithms for decomposable convex programs, On connectionist models, An approach to the construction of approximate solutions of Boolean linear programming problems, Convergence of a cyclic ellipsoid algorithm for systems of linear equalities, Modifications and implementation of the ellipsoid algorithm for linear programming, Optimal scaling of balls and polyhedra, Investigation of optimization methods and their applications, The Average number of pivot steps required by the Simplex-Method is polynomial, Linear Programming with Inexact Data is NP‐Hard