Improved polynomial algorithms for robust bottleneck problems with interval data

DOI10.1016/J.COR.2009.03.013MaRDI QIDQ1046706zbMATH OpenOpenAlexFDO

Authors A. Volgenant, Cees Duin

Publication date 22 December 2009

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2009.03.013

zbMATH Keywords

bottleneck criterioninterval dataminmax regretsequencing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• Interval data minmax regret network optimization problems
• On the complexity of a class of combinatorial optimization problems with uncertainty
• Minmax regret solutions for minimax optimization problems with uncertainty
• Algorithms for the robust 1-center problem on a tree

Cites work

• Algorithms for two bottleneck optimization problems
• An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem
• An augmenting path method for solving linear bottleneck assignment problems
• An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem
• Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion
• Minmax regret solutions for minimax optimization problems with uncertainty
• On the complexity of the robust spanning tree problem with interval data
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints
• Robust discrete optimization and its applications
• The computational complexity of the relative robust shortest path problem with interval data
• The partial sum criterion for Steiner trees in graphs and shortest paths
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees

Cited in

(6)

• Minimizing maximum cost for a single machine under uncertainty of processing times
• Lawler's minmax cost problem under uncertainty
• Sensitivity analysis for bottleneck assignment problems
• Single machine scheduling problems with uncertain parameters and the OWA criterion
• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion

This page was built for publication: Improved polynomial algorithms for robust bottleneck problems with interval data

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