Some concepts of stability analysis in combinatorial optimization

DOI10.1016/0166-218X(93)E0126-JzbMath0833.90098MaRDI QIDQ1805456

V. K. Leont'ev, Yuri N. Sotskov, Eh. N. Gordeev

Publication date: 17 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

stability analysis for discrete optimization; stability ball of optimal or approximate solutions

Mathematics Subject Classification ID

05C05: Trees

90C31: Sensitivity, stability, parametric optimization

90B35: Deterministic scheduling theory in operations research

90C27: Combinatorial optimization

05C38: Paths and cycles

90B80: Discrete location and assignment

Related Items

A general approach to studying the stability of a Pareto optimal solution of a vector integer linear programming problem, On the Hardness of Reoptimization, Analyse de sensibilité pour les problèmes linéaires en variables 0-1, An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual, Approximating the stability region for binary mixed-integer programs, On combinatorial optimization problems on matroids with uncertain weights, Approximation hardness of deadline-TSP reoptimization, Stability aspects of the traveling salesman problem based on \(k\)-best solutions, On the quasistability of trajectory problems of vector optimization, On the complexity of postoptimality analysis of \(0/1\) programs, Calculation of stability radii for combinatorial optimization problems, Stability of a schedule minimizing mean flow time, Optimal makespan scheduling with given bounds of processing times, On a measure of quasistability of a certain vector linearly combinatorial Boolean problem, General approach to estimating the complexity of postoptimality analysis for discrete optimization problems, Reoptimization of the metric deadline TSP, Stability and accuracy functions in multicriteria linear combinatorial optimization problems, Boolean problem of sequential minimization of moduli of linear functions and stability theorems, Stability radius of a lexicographic optimum of a vector problem of Boolean programming, Sensitivity analysis in the single-machine scheduling problem with max-min criterion, On stability of a vector combinatorial problem with MINMIN criteria, Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem, Reoptimization of the Metric Deadline TSP

Cites Work

• A note on two problems in connexion with graphs
• A review of the static, stochastic job sequencing literature
• Stability in bottleneck path problems
• Stability of an optimal schedule
• The stability of the approximate Boolean minimization of a linear form
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Stochastic scheduling problems I — General strategies
• Sensitive and parametric analysis of the maximum flow in a network
• A problem in scheduling theory
• A General Framework for Stochastic One-machine Scheduling Problems with Zero Release Times and No Partial Ordering
• A note on Arc tolerances in sparse shortest-path and network flow problems
• Solution of a parametric integer programming problem
• Computational algorithms for finding the radius of stability in problems of choice
• Parametric trajectory problems
• Stochastic scheduling problems II-set strategies-
• Complexity of some parametric integer and network programming problems
• Independent flows with a discrete-concave expenditure function
• On the Numerical Stability of Simplex-Algorithms
• Steiner problem in networks: A survey
• Algorithms of polynomial complexity for computing the radius of instability in two classes of trajectory problems
• Arc tolerances in shortest path and network flow problems
• Integer programming duality: Price functions and sensitivity analysis
• Sensitivity analysis of optimal matchings
• A shortest augmenting path method for solving minimal perfect matching problems
• The value function of an integer program
• Stability in bottleneck problems
• Postoptimality analysis in integer programming by implicit enumeration: The mixed integer case
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• A Characterization of Stability in Linear Programming
• Optimal schedules with infinitely large stability radius^∗
• Sensitivity Analysis of Multiterminal Flow Networks
• Stability in Nonlinear Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item