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)

A framework for the complexity of high-multiplicity scheduling problems
Eigenvectors of interval matrices over max--plus algebra
Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance
A Variable-Complexity Norm Maximization Problem
On the frontiers of polynomial computations in tropical geometry
A new approach to the learning effect: Beyond the learning curve restrictions
Randomized methods for the number partitioning problem
Distributed asynchronous computation of fixed points
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
A study of complexity transitions on the asymmetric traveling salesman problem
A class of bounded approximation algorithms for graph partitioning
Computing a Sparse Basis for the Null Space
Optimal Matching and Empirical Measures
Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound
Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems
The NPO-completeness of the longest Hamiltonian cycle problem
On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
Approximate solution of NP optimization problems
Complexity of unification problems with associative-commutative operators
A sum of disjoint products algorithm for reliability evaluation of flow networks
Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility
Completeness in approximation classes
Minimum distance index for complex valued ICA
Optimal due date assignment in multi-machine scheduling environments
Old and new results on algebraic connectivity of graphs
Approximation algorithms for combinatorial fractional programming problems
An alternative approach for proving the NP-hardness of optimization problems
Robust optimization of the 0-1 knapsack problem: balancing risk and return in assortment optimization
Mining approximate interval-based temporal dependencies
A survey on metaheuristics for stochastic combinatorial optimization
Multiplicity and complexity issues in contemporary production scheduling
Optimal search path for service in the presence of disruptions
A memetic algorithm for graph coloring
Title not available (Why is that?)
Polyhedral proof methods in combinatorial optimization
Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities
A simulated annealing approach to police district design
Interior path following primal-dual algorithms. I: Linear programming
Cluster analysis for portfolio optimization
Local minima for indefinite quadratic knapsack problems
New crash procedures for large systems of linear constraints
Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities
Lexicographic bottleneck combinatorial problems
Approximation algorithms for a geometric set cover problem
A primal-dual simplex algorithm for bi-objective network flow problems
Experiments on the minimum linear arrangement problem
Models and solution techniques for frequency assignment problems
Two due date assignment problems in scheduling a single machine
Heuristic solutions and confidence intervals for the multicovering problem
Capacitated lot-sizing and scheduling by Lagrangean relaxation
A large step random walk for minimizing total weighted tardiness in a job shop
The job shop scheduling problem: Conventional and new solution techniques
Scheduling with job-dependent learning effects and multiple rate-modifying activities
Large gaps in one-dimensional cutting stock problems
Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application
On worst-case aggregation analysis for network location problems
Tabu search for the job-shop scheduling problem with multi-purpose machines
Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments
``Product partition and related problems of scheduling and systems reliability: computational complexity and approximation
Hybridizing exact methods and metaheuristics: a taxonomy
Local search algorithms for a single-machine scheduling problem with positive and negative time-lags
Single-machine scheduling with learning considerations
Classification of applied methods of combinatorial optimization
Digraph matrix partitions and trigraph homomorphisms
Parallel machine scheduling with a common server
A hierarchical algorithm for making sparse matrices sparser
A constrained matching problem
Locating flow-capturing units on a network with multi-counting and diminishing returns to scale
A proposal for a hybrid meta-strategy for combinatorial optimization problems
Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems
Pseudopolynomial algorithms for CTV minimization in single machine scheduling
Computational complexity of a problem arising in fixed order output feedback design
Linear combinations of heuristics for examination timetabling
An extension of Karmarkar's projective algorithm for convex quadratic programming
A multiperiod traveling salesman problem: Heuristic algorithms
Optimal due-date assignment and sequencing
Solving combinatorial optimization problems using Karmarkar's algorithm
The multicovering problem
A mathematical model and a solution method for the problem of placing various-sized circles into a strip
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Complexity of the Frobenius problem
Two parallel machine sequencing problems involving controllable job processing times
Simulated annealing and tabu search in the long run: A comparison on QAP tasks
A robust heuristic for the generalized assignment problem
Minimum vertex cover in ball graphs through local search
ETSAP-TIAM: The TIMES integrated assessment model. I: Model structure
Single machine scheduling to minimize total weighted tardiness
Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction
Annealed replication: A new heuristic for the maximum clique problem
A linear time algorithm for maximum matchings in convex, bipartite graphs
Metaheuristics: A bibliography
Exact and heuristic approaches based on noninterfering transmissions for joint gateway selection, time slot allocation, routing and power control for wireless mesh networks
Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint
Hybrid metaheuristics: an introduction
A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time
A new heuristic for the period traveling salesman problem
Algorithms and codes for dense assignment problems: The state of the art
Locating a low-level waste disposal site
SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
A survey of heuristics for the weighted matching problem

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)