scientific article; zbMATH DE number 3793772

zbMATH Open0503.90060MaRDI QIDQ4739657FDOQ4739657

Authors: Ken Steiglitz, Christos Papadimitriou

Publication date: 1982

Title of this publication is not available (Why is that?)

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

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

Optimal strategies for some team games
On the stability of asynchronous iterative processes
Multitask \(n\)-vehicle exploration problem: complexity and algorithm
Simultaneous mesh generation and partitioning for Delaunay meshes
A new and improved algorithm for the 3-cut problem
A set covering reformulation of the pure fixed charge transportation problem
Concerning the achromatic number of graphs
A condition for the strong regularity of matrices in the minimax algebra
Decomposition representations of logical equations in problems of inversion of discrete functions
A measure-theoretical max-flow-min-cut problem
Performances of parallel branch and bound algorithms with best-first search
Canadian traveller problem with predictions
Computing the bump number is easy
Constrained matroidal bottleneck problems
Interval propagation to reason about sets: Definition and implementation of a practical language
The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate
Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis
On the computational complexity of coalitional resource games
Representability in mixed integer programming. I: Characterization results
The complexity of multidimensional periodic scheduling
Complexity of matching problems
Probabilistic construction of deterministic algorithms: approximating packing integer programs
Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
Tropical linear maps on the plane
Combinatorial optimization techniques for spacecraft scheduling automation
Primal-dual target-following algorithms for linear programming
The optimum execution order of queries in linear storage
Additivity obstructions for integral matrices and pyramids
Stochastic global optimization as a filtering problem
Correlation based networks of equity returns sampled at different time horizons
Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour
A Lagrangean relaxation method for the constrained assignment problem
An algorithm for the detection and construction of Monge sequences
Guarding a set of line segments in the plane
A combined analytical, numerical, and experimental study of shape-memory-alloy helical springs
A unified approach for scheduling with convex resource consumption functions using positional penalties
THE NP-HARDNESS OF MINIMIZING THE TOTAL LATE WORK ON AN UNBOUNDED BATCH MACHINE
Approximating shortest superstrings with constraints
Algorithms for the transportation problem in geometric settings
An inverse problem of the weighted shortest path problem
Ascending price Vickrey auctions for general valuations
On ascending Vickrey auctions for heterogeneous objects
Reasoning about qualitative temporal information
Single-machine Scheduling Problems with Aging/Deteriorating Effect under an Optional Maintenance Activity Consideration
Experimental results on quadrangulations of sets of fixed points
Solving 0-1 programming problems by a penalty approach.
Global optimization for the biaffine matrix inequality problem
TSP ejection chains
The travelling salesman problem: selected algorithms and heuristics†
Treatment of combinatorial optimization problems using selection equations with cost terms. II: NP-hard three-dimensional assignment problems
Treatment of combinatorial optimization problems using selection equations with cost terms. I: Two-dimensional assignment problems
Relaxed tours and path ejections for the traveling salesman problem
Computation of the solutions of nonlinear polynomial systems
Using a greedy random adaptative search procedure to solve the cover printing problem
Games against nature
Length-bounded disjoint paths in planar graphs
On a decision procedure for quantified linear programs
Parallel ILP for distributed-memory architectures
A quasiconcave minimization method for solving linear two-level programs
Simple characterizations of \(P(\# P)\) and complete problems
A resampling approach to cluster validation
On a dynamic auction mechanism for a bilateral assignment problem
Experimental study on approximation algorithms for guarding sets of line segments
The generalized linear complementarity problem and an algorithm to find all its solutions
The Null Space Problem II. Algorithms
Adjusted interval digraphs
Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling
A nonmonotone GRASP
Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
A rescheduling and cost allocation mechanism for delayed arrivals
The routing open-shop problem on a network: complexity and approximation
Algorithms of discrete optimization and their application to problems with fuzzy coefficients
Constant factor approximation algorithm for TSP satisfying a biased triangle inequality
Interpretable clustering using unsupervised binary trees
Optimal due date assignment and resource allocation in a group technology scheduling environment
Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
Optimal dynamic routing in communication networks with continuous traffic
A dynamic tabu search for large-scale generalized assignment problems
Disjoint pattern database heuristics
The capacity expansion path problem in networks
Classifying the computational complexity of problems
Copositive realxation for genera quadratic programming
Approximate algorithms for the Knapsack problem on parallel computers
Greedily constructing maximal partial \(f\)-factors
RESAMPLING FOR FUZZY CLUSTERING
A weighted min-max relation for intervals
A class of bottleneck expansion problems
Scheduling under a common due-date on parallel unrelated machines
Maximizing the value of a space mission
On the core of routing games
Planning of high school examinations in Denmark
Unit commitment in oligopolistic markets by nonlinear mixed variable programming
A column generation method for inverse shortest path problems
Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
Local search: is brute-force avoidable?
On players with a bounded number of states
On the complexity of the unit commitment problem
Minimum deviation problems
Single-machine scheduling and slack due-date assignment with aging effect and deteriorating maintenance
Correlation polytopes: Their geometry and complexity

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4739657)