scientific article
From MaRDI portal
Publication:3050157
zbMath0414.90086MaRDI QIDQ3050157
Publication date: 1979
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexityvector optimizationpolynomial algorithmsimplex methodpolynomial solvabilitycomplex linear programming
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05)
Related Items
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, Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization, Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic, Geometric random edge, A practical implementation of stochastic programming: an application to the evaluation of option contracts in supply chains, Buying optimal payoffs in bi-matrix games, 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, Tropically convex constraint satisfaction, Bounded self-stabilizing Petri nets, A primal-dual interior point method whose running time depends only on the constraint matrix, On PAC learning algorithms for rich Boolean function classes, Solving linear programming problems exactly, Optimization of computations, Linear programming, the simplex algorithm and simple polytopes, Interior-point methods: An old and new approach to nonlinear programming, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, Complexity of evolution in maximum cooperative P systems, Identifying an optimal basis in linear programming, On properties of unit interval graphs with a perceptual motivation, Some directions and results of research in mathematical programming and system analysis, A potential reduction approach to the frequency assignment problem, 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, Task assignment in tree-like hierarchical structures, Some thoughts on combinatorial optimisation, Abstract tropical linear programming, A global optimization algorithm for solving a four-person game, On tail dependence matrices. The realization problem for parametric families, An improved ellipsoid method for solving convex differentiable optimization problems, Automated competitive analysis of real-time scheduling with graph games, Some \(0/1\) polytopes need exponential size extended formulations, An entire space polynomial-time algorithm for linear programming, Optimal deviations from an asset allocation., Generalized max flow in series-parallel graphs, Specialized fast algorithms for IQC feasibility and optimization problems., Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems, An algorithmic separating hyperplane theorem and its applications, On complexity of matrix scaling, A direct heuristic algorithm for linear programming, Algorithms for bivariate zonoid depth, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, On the computational behavior of a polynomial-time network flow algorithm, Modified Fourier's method of solving linear programming problems., Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming, On a graph partition problem with application to VLSI layout, How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, An optimal randomized algorithm for \(d\)-variate zonoid depth, Partitioned EDF scheduling on a few types of unrelated multiprocessors, Approximation algorithms for the max-buying problem with limited supply, A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, On quantified linear implications, Linear programming in \(O(n\times 3^{d^2})\) time, A hierarchical solution approach for a multicommodity distribution problem under a special cost structure, Approximation algorithms for geometric median problems, A novel convex dual approach to three-dimensional assignment problem: theoretical analysis, The asymptotic optimal partition and extensions of the nonsubstitution theorem, Optimal preemptive scheduling on a fixed number of identical parallel machines, Systems of linear equations with fuzzy set data: weak solvability and weak admissibility, Improved complexity results on solving real-number linear feasibility problems, Evaluating the impact of AND/OR search on 0-1 integer linear programming, An AGM-style belief revision mechanism for probabilistic spatio-temporal logics, Using selective orthonormalization to update the analytic center after addition of multiple cuts, Near-optimal no-regret algorithms for zero-sum games, Bayesian incentive compatibility via matchings, On approximation algorithms for concave mixed-integer quadratic programming, Supporting dynamic updates in storage clouds with the Akl-Taylor scheme, On max-flow min-cut and integral flow properties for multicommodity flows in directed networks, Algorithmic reduction of biological networks with multiple time scales, The gap between monotone and non-monotone circuit complexity is exponential, Containing and shrinking ellipsoids in the path-following algorithm, Piecewise linear valued constraint satisfaction problems with fixed number of variables, Deriving Karmarkar's LP algorithm using angular projection matrix, A note on the approximability of deepest-descent circuit steps, A unifying approach to temporal constraint reasoning, Fast finite methods for a system of linear inequalities, Single machine scheduling subject to deadlines and resource dependent processing times, A general lower bound on the number of examples needed for learning, Probabilistic game automata, Main directions in the development of informatics, \(O(n^ 3)\) noniterative heuristic algorithm for linear programs with error-free implementation., On the linear ordering problem and the rankability of data, The minimum mean cycle-canceling algorithm for linear programs, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, Sinkhorn-Knopp theorem for PPT states, On the complexity of finding a local minimizer of a quadratic function over a polytope, 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, Symbiosis between linear algebra and optimization, Academician V. S. Mikhalevich as a scientist and science organizer (on the occasion of his 70th birthday), An exterior point polynomial-time algorithm for convex quadratic programming, A characterization theorem and an algorithm for a convex hull problem, A semantical framework for supporting subjective and conditional probabilities in deductive databases, A deep cut ellipsoid algorithm for convex programming: Theory and applications, MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations, Solving Linear Programming with Constraints Unknown, Exact Incremental Analysis of Timed Automata with an SMT-Solver, Even circuits in oriented matroids, The polynomial hierarchy and a simple model for competitive analysis, On box totally dual integral polyhedra, A Variable-Complexity Norm Maximization Problem, Using Nemirovski's Mirror-Prox method as basic procedure in Chubanov's method for solving homogeneous feasibility problems, Linear equations for unordered data vectors in $[D^k\to{}Z^d$], From Parity and Payoff Games to Linear Programming, A class of convergent primal-dual subgradient algorithms for decomposable convex programs, On computational complexity of construction of c -optimal linear regression models over finite experimental domains, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming, Regular triangulations and Steiner points, Some recognition problems related to graph isomorphism, Approximating Scheduling Machines with Capacity Constraints, Incentive Stackelberg Mean-Payoff Games, The price of defense, On the complexity of nucleolus computation for bipartite \(b\)-matching games, Parameterized Weighted Containment, A Class of Balanced Matrices Arising from Location Problems, An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains, Subgradient ellipsoid method for nonsmooth convex problems, Approximability results for the $p$-centdian and the converse centdian problems, Explicit explore, exploit, or escape \((E^4)\): near-optimal safety-constrained reinforcement learning in polynomial time, Polynomial-time data reduction for weighted problems beyond additive goal functions, Complexity of optimizing over the integers, Synthesis of parametric hybrid automata from time series, An infeasible interior-point technique to generate the nondominated set for multiobjective optimization problems, Restricted Gröbner fans and re-embeddings of affine algebras, The octatope abstract domain for verification of neural networks, Robust optimization for minimizing energy consumption of multicast transmissions in coded wireless packet networks under distance uncertainty, Revisiting security estimation for LWE with hints from a geometric perspective, How Do Exponential Size Solutions Arise in Semidefinite Programming?, Eigenpolytope Universality and Graphical Designs, The computability of LQR and LQG control, The maximin support method: an extension of the d'Hondt method to approval-based multiwinner elections, Hardness Results for Structured Linear Systems, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, On connectionist models, Resolvability of Hamming Graphs, A Friendly Smoothed Analysis of the Simplex Method, McCulloch-Pitts Brains and Pseudorandom Functions, Constraint Satisfaction Problems over Numeric Domains, On the complexity of problems on simple games, SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, An extension of Chubanov's polynomial-time linear programming algorithm to second-order cone programming, An improved version of Chubanov's method for solving a homogeneous feasibility problem, Voting Procedures, Complexity of, METHOD FOR SEQUENTIAL ACTIVATION OF LIMITATIONS IN LINEAR PROGRAMMING, An approach to the construction of approximate solutions of Boolean linear programming problems, A simple polynomial-time rescaling algorithm for solving linear programs, A class of rank-two ellipsoid algorithms for convex programming, On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method, Application of the ellipsoid method in an interactive procedure for multicriteria linear programming, Max-Closed Semilinear Constraint Satisfaction, The History of the LLL-Algorithm, Resolution Width and Cutting Plane Rank Are Incomparable, Unnamed Item, Graph transformations preserving the stability number, Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning, Complexity aspects of a semi-infinite optimization problem†, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Newton–Ellipsoid polynomiography, Trace Refinement in Labelled Markov Decision Processes, Generating all vertices of a polyhedron is hard, The Stable Fixtures Problem with Payments, Unnamed Item, POINTWISE RESIDUAL METHOD FOR SOLVING PRIMAL AND DUAL ILL-POSED LINEAR PROGRAMMING PROBLEMS WITH APPROXIMATE DATA, Book Review: The basic George B. Dantzig, Conflict Analysis for MINLP, Khachiyan's Algorithmus, Unnamed Item, 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, On transformation of conditional, conformant and parallel planning to linear programming, Linear Programming with Inexact Data is NP‐Hard, Method of ellipsoids, its generalizations and applications, Investigation of optimization methods and their applications, The Average number of pivot steps required by the Simplex-Method is polynomial, Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games, A quantum interior-point predictor–corrector algorithm for linear programming, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
