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)

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 ⋮ Repairing high school timetables with polymorphic ejection chains ⋮ The NPO-completeness of the longest Hamiltonian cycle problem ⋮ Near-optimal nonapproximability results for some \textsc{Npo} PB-complete problems ⋮ On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem ⋮ Minimum distance index for complex valued ICA ⋮ Single machine scheduling with two competing agents and equal job processing times ⋮ 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 nonmonotone GRASP ⋮ A rescheduling and cost allocation mechanism for delayed arrivals ⋮ Constant factor approximation algorithm for TSP satisfying a biased triangle inequality ⋮ Interpretable clustering using unsupervised binary trees ⋮ Graph properties checkable in linear time in the number of vertices ⋮ The capacity expansion path problem in networks ⋮ Unit commitment in oligopolistic markets by nonlinear mixed variable programming ⋮ New perspectives in VLSI design automation: deterministic packing by sequence pair ⋮ A hybrid search method for the vehicle routing problem with time windows ⋮ Multitask \(n\)-vehicle exploration problem: complexity and algorithm ⋮ Decomposition representations of logical equations in problems of inversion of discrete functions ⋮ An effective multilevel tabu search approach for balanced graph partitioning ⋮ Minimizing the total completion time in single-machine scheduling with aging/deteriorating effects and deteriorating maintenance activities ⋮ On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices ⋮ Algorithmic paradigms for stability-based cluster validity and model selection statistical methods, with applications to microarray data analysis ⋮ Stochastic global optimization as a filtering problem ⋮ Guarding a set of line segments in the plane ⋮ Approximation algorithms for a geometric set cover problem ⋮ Local search: is brute-force avoidable? ⋮ Scheduling with job-dependent learning effects and multiple rate-modifying activities ⋮ Scheduling with learning effects and/or time-dependent processing times to minimize the weighted number of tardy jobs on a single machine ⋮ Timetable construction: the algorithms and complexity perspective ⋮ The design and implementation of an interactive course-timetabling system ⋮ Minimum energy control and optimal-satisfactory control of Boolean control network ⋮ Exploring the tractability border in epistemic tasks ⋮ Optimal portfolio allocation under the probabilistic VaR constraint and incentives for financial innovation ⋮ Computational complexity of convoy movement planning problems ⋮ Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities ⋮ Approximate solution of NP optimization problems ⋮ The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate ⋮ Minimizing maximum weight of subsets of a maximum matching in a bipartite graph ⋮ Scheduling on a single processor with variable speed ⋮ Knapsack problems for NL ⋮ Training digraphs ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Nash equilibria in the two-player kidney exchange game ⋮ Interval propagation to reason about sets: Definition and implementation of a practical language ⋮ Resource constrained scheduling with general truncated job-dependent learning effect ⋮ Automatic construction of parallel portfolios via algorithm configuration ⋮ Disturbance rejection control based on state-reconstruction and persistence disturbance estimation ⋮ Dynamic algorithms for shortest paths in planar graphs ⋮ A genuinely polynomial primal simplex algorithm for the assignment problem ⋮ Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices ⋮ Approximation algorithms for indefinite quadratic programming ⋮ Scheduling with job-rejection and position-dependent processing times on proportionate flowshops ⋮ A primal-dual simplex method for linear programs ⋮ Complexity of unification problems with associative-commutative operators ⋮ A generalized hypergreedy algorithm for weighted perfect matching ⋮ A long-step barrier method for convex quadratic programming ⋮ Geometric Knapsack problems ⋮ On worst-case aggregation analysis for network location problems ⋮ Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches ⋮ The generic canonical form of a regular structured matrix pencil ⋮ A survey of very large-scale neighborhood search techniques ⋮ Due-window assignment and scheduling with multiple rate-modifying activities under the effects of deterioration and learning ⋮ Weighted argument systems: basic definitions, algorithms, and complexity results ⋮ Local ratio with negative weights. ⋮ Tropical linear maps on the plane ⋮ Block linear majorants in quadratic 0--1 optimization ⋮ Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments ⋮ Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble ⋮ A new look at the automatic synthesis of linear ranking functions ⋮ Optimal search path for service in the presence of disruptions ⋮ Heuristic solutions and confidence intervals for the multicovering problem ⋮ A measure-theoretical max-flow-min-cut problem ⋮ A simpler and faster algorithm for optimal total-work-content-power due data determination ⋮ A dynamic location problem for graphs ⋮ Cyclic orders ⋮ Scheduling periodic events ⋮ New crash procedures for large systems of linear constraints ⋮ Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problems ⋮ Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time ⋮ Approximation algorithms for three-dimensional assignment problems with triangle inequalities ⋮ Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies ⋮ Resource allocation under limited sharing ⋮ Making sparse matrices sparser: Computational results ⋮ A level set algorithm for a class of reverse convex programs ⋮ Active set algorithms for isotonic regression; a unifying framework ⋮ Approximate algorithms for the Knapsack problem on parallel computers ⋮ An optimization model and a solution algorithm for the many-to-many car pooling problem ⋮ Recent trends in combinatorial optimization ⋮ Network models for vehicle and crew scheduling ⋮ Certain NP-complete matching problems ⋮ On monotonicity in the scaled potential algorithm for linear programming ⋮ Theoretical efficiency of a shifted-barrier-function algorithm for linear programming ⋮ On the regularity of matrices in min algebra ⋮ Shortest paths without a map

This page was built for publication: