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)

ParadisEO-MO: from fitness landscape analysis to efficient local search algorithms
Asymptotics for transportation cost in high dimensions
Lower bounds for resolution and cutting plane proofs and monotone computations
Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
Sums of idempotents and logarithmic residues in zero pattern matrix algebras
Hybrid constructive heuristics for the critical node problem
Weighted digraphs and tropical cones
Representations of votes facilitating monotonicity-based ranking rules: from votrix to votex
Resource allocation under limited sharing
Graph properties checkable in linear time in the number of vertices
Exact credal treatment of missing data
Single machine scheduling with two competing agents and equal job processing times
The nucleolus of balanced simple flow networks
Geometric Knapsack problems
Graph colourings and partitions
Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
Repairing high school timetables with polymorphic ejection chains
The complexity of facets resolved
An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
On the polyhedral complexity of the integer points in a hyperball
GRAFT, a complete system for data fusion
Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
Scaling algorithms for network problems
Scheduling jobs with fixed start and end times
Dual coordinate step methods for linear network flow problems
Timetable construction: the algorithms and complexity perspective
Variable neighborhood search: Principles and applications
Future paths for integer programming and links to artificial intelligence
Temporal constraint networks
Auction algorithms for network flow problems: A tutorial introduction
A new mathematical model for tiling finite regions of the plane with polyominoes
On the maximum size of Erdős-Ko-Rado sets in \(H(2d+1, q^2)\)
On the complexity and approximation of syntenic distance
A state-of-the-art review of parallel-machine scheduling research
Some results concerning post-infeasibility analysis
On-line algorithms for weighted bipartite matching and stable marriages
Approximation algorithms for indefinite quadratic programming
A survey of very large-scale neighborhood search techniques
On visualization scaling, subeigenvectors and Kleene stars in max algebra
The complexity of determining a shortest cycle of even length
On the robust shortest path problem.
Optimal resource allocation with minimum activation levels and fixed costs
Shortest paths without a map
Heuristic and exact algorithms for the simultaneous assignment problem
The traveling salesman problem: An overview of exact and approximate algorithms
An effective hybrid algorithm for university course timetabling
A dynamic location problem for graphs
Strong regularity of matrices -- a survey of results
How easy is local search?
An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
A branch and bound algorithm for the resource-constrained project scheduling problem
On finding optimal and near-optimal lineal spanning trees
A linear time algorithm for graph partition problems
Characterizations of consistent marked graphs
Formulating logical implications in combinatorial optimisation
The complexity of facets (and some facets of complexity)
The hierarchical network design problem
An integer programming problem and rank decomposition of block upper triangular matrices
The general maximum matching algorithm of Micali and Vazirani
A primal-dual interior point method whose running time depends only on the constraint matrix
Interior path following primal-dual algorithms. II: Convex quadratic programming
On the solution of concave knapsack problems
On the complexity of generalized due date scheduling problems
The uniquely solvable bipartite matching problem
Finding minimum-cost flows by double scaling
Beam-ACO--hybridizing ant colony optimization with beam search: an application to open shop scheduling
An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
Converting triangulations to quadrangulations
The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
Finding a complete matching with the maximum product on weighted bipartite graphs
A branch and bound algorithm for symmetric 2-peripatetic salesman problems
Reverse search for enumeration
Ant colony optimization theory: a survey
The \(Multi\)-SAT algorithm
The minimum shift design problem
Two phase algorithms for the bi-objective assignment problem
The complexity of resource allocation and price mechanisms under bounded rationality
Greedy randomized adaptive search procedures
Efficient text fingerprinting via Parikh mapping
DNA solution of integer linear programming
The logarithmic HLS inequality for systems on compact manifolds
Selfish unsplittable flows
Optimization and testing in linear non‐Gaussian component analysis
Computing the bipartite edge frustration of fullerene graphs
Adaptive tabu search for course timetabling
Project scheduling under competition
Solving a cutting-stock problem with the constraint logic programming language CHIP
Solving real-life vehicle routing problems efficiently using tabu search
A general trimming approach to robust cluster analysis
Using combinatorial optimization in model-based trimmed clustering with cardinality constraints
Approximation algorithms for three-dimensional assignment problems with triangle inequalities
Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies
Dealing with label switching in mixture models under genuine multimodality
An Exact Distribution-Free Test Comparing Two Multivariate Distributions based on Adjacency
\(\mathcal {NPD}\)atalog: A logic language for expressing \(\mathcal {NP}\) search and optimization problems
A shortest augmenting path algorithm for dense and sparse linear assignment problems
Generalized probabilistic satisfiability
The auction algorithm: A distributed relaxation method for the assignment problem
Active set algorithms for isotonic regression; a unifying framework
Approximation algorithms for multi-dimensional assignment problems with decomposable costs

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)