scientific article; zbMATH DE number 3793772

Kenneth Steiglitz, Christos H. Papadimitriou

Publication date: 1982

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

combinatorial optimization ellipsoid algorithm NP-completeness matroids complexity theory polynomial time algorithms network flow problems shortest path problems spanning tree problem matching problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Deterministic network models in operations research (90B10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01)

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

Approximation algorithms for multi-dimensional assignment problems with decomposable costs ⋮ Some results concerning post-infeasibility analysis ⋮ Complexity of a class of nonlinear combinatorial problems related to their linear counterparts ⋮ An ordered independence system and its applications to scheduling problems ⋮ Efficient inference in Bayes networks as a combinatorial optimization problem ⋮ Simple characterizations of \(P(\# P)\) and complete problems ⋮ The hybrid spanning tree problem ⋮ Simulated annealing and tabu search in the long run: A comparison on QAP tasks ⋮ Primal-dual algorithms for linear programming based on the logarithmic barrier method ⋮ On problems with short certificates ⋮ Objects that cannot be taken apart with two hands ⋮ A robust heuristic for the generalized assignment problem ⋮ Combinatorial optimization techniques for spacecraft scheduling automation ⋮ Maximum number of disjoint paths connecting specified terminals in a graph ⋮ A bicriterion objective for levelling the schedule of a mixed-model, \(JIT\) assembly process ⋮ Some properties of the Hessian of the logarithmic barrier function ⋮ Approximating shortest superstrings with constraints ⋮ A Lagrangean heuristic for the capacitated concave minimum cost network flow problem ⋮ Maximizing the value of a space mission ⋮ The traveling salesman problem with delivery and backhauls ⋮ Tabu search performance on the symmetric travelling salesman problem ⋮ On-line algorithms for weighted bipartite matching and stable marriages ⋮ An algorithm for an Eulerian trail traversing specified edges in given order ⋮ Polynomial algorithms for linear programming over the algebraic numbers ⋮ On the magnetisation of the ground states in two dimensional Ising spin glasses ⋮ Asymptotics for transportation cost in high dimensions ⋮ Regularity of matrices in min-algebra and its time-complexity ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ New local search approximation techniques for maximum generalized satisfiability problems ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ A note on determining pure-strategy equilibrium points of bimatrix games ⋮ Some results on the computational complexity of symmetric connectionist networks. ⋮ A hypergraph model for constraint logic programming and applications to bus drivers' scheduling ⋮ The determinant of a tree's neighborhood matrix ⋮ Vertex heaviest paths and cycles in quasi-transitive digraphs ⋮ Alternating cycles and paths in edge-coloured multigraphs: A survey ⋮ On the core of routing games ⋮ Deriving constraints among argument sizes in logic programs ⋮ On the solvability problem for equations with a single coefficient ⋮ On linear programming and matrix scaling over the algebraic numbers ⋮ Inverse matroid intersection problem ⋮ A branch \(\&\) bound algorithm for the open-shop problem ⋮ TSP ejection chains ⋮ Measure concentration in optimization ⋮ Massively parallel augmenting path algorithms for the assignment problem ⋮ On a dynamic auction mechanism for a bilateral assignment problem ⋮ An efficient P-D algorithm for shortest path problem ⋮ The \(\beta\)-assignment problem in general graphs ⋮ Effective assignment algorithm for continuous two-stage activities in loading and transportation management ⋮ Mechanisms for local search ⋮ A heuristic for blocking flow algorithms ⋮ A new and improved algorithm for the 3-cut problem ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Parallel processing for difficult combinatorial optimization problems ⋮ General information dispersal algorithms ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Randomized Boolean decision trees: Several remarks ⋮ The life span method -- a new variant of local search ⋮ A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays ⋮ Solvability of the vector problem by the linear criteria convolution algorithm ⋮ Locating flow-capturing units on a network with multi-counting and diminishing returns to scale ⋮ Price-directive decomposition applied to routing in telecommunication networks ⋮ Algorithms for network piecewise-linear programs: A comparative study ⋮ Routing trains through railway stations: Complexity issues ⋮ Formalization of the class of problems solvable by a nondeterministic Turing machine ⋮ The complexity of multidimensional periodic scheduling ⋮ A \(2_3^2\) superstring approximation algorithm ⋮ On the complexity and approximation of syntenic distance ⋮ Genotyping of pooled microsatellite markers by combinatorial optimization techniques ⋮ Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application ⋮ The \(\beta\)-assignment problems ⋮ Scheduling under a common due-date on parallel unrelated machines ⋮ An optimal tree search method for the manufacturing systems cell formation problem ⋮ Improved exploration in Hopfield network state-space through parameter perturbation driven by simulated annealing ⋮ A branch and bound algorithm for the resource-constrained project scheduling problem ⋮ Classical and new heuristics for the open-shop problem: A computational evaluation ⋮ A general approach to solving a wide class of fuzzy optimization problems ⋮ Persistency in the assignment and transportation problems ⋮ Lexicographic bottleneck combinatorial problems ⋮ A branch and bound algorithm for symmetric 2-peripatetic salesman problems ⋮ A model for the assignment of candidates to constituencies in a mixed election system ⋮ Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times ⋮ Two parallel machine sequencing problems involving controllable job processing times ⋮ An overview of median and stack filtering ⋮ The knapsack program generator of fractal curves with random stopping rule ⋮ Strong regularity of matrices -- a survey of results ⋮ Some new results regarding spikes and a heuristic for spike construction ⋮ A generic auction algorithm for the minimum cost network flow problem ⋮ Parallel primal-dual methods for the minimum cost flow problem ⋮ Computation of the solutions of nonlinear polynomial systems ⋮ A greedy heuristic for a minimum-weight forest problem ⋮ A set covering reformulation of the pure fixed charge transportation problem ⋮ Stable marriage and indifference ⋮ Tabu search for the job-shop scheduling problem with multi-purpose machines ⋮ A quasiconcave minimization method for solving linear two-level programs ⋮ Computability, complexity and economics ⋮ The auction algorithm: A distributed relaxation method for the assignment problem ⋮ Series parallel composition of greedy linear programming problem ⋮ Designing secure communication protocols from trust specifications ⋮ Approximate kinodynamic planning using \(L_ 2\)-norm dynamic bounds

This page was built for publication: