Reoptimization of set covering problems

DOI10.1007/S10559-010-9269-ZMaRDI QIDQ2247803zbMATH OpenOpenAlexFDO

Authors Victor A. Mikhailyuk

Publication date 30 June 2014

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10559-010-9269-z

zbMATH Keywords

reoptimization\(r\)-approximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Recommendations

• Reoptimization of max \(k\)-cover: approximation ratio threshold
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• Reoptimization of Weighted Graph and Covering Problems
• An O(m n) algorithm for regular set-covering problems
• Online and dynamic algorithms for set cover

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimizing the 0-1 knapsack problem
• Reoptimizing the traveling salesman problem
• Simple and fast reoptimizations for the Steiner tree problem

Cited in

(8)

• On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field
• scientific article; zbMATH DE number 1354909 (Why is no real title available?)
• Reoptimization of NP-Hard Problems
• Reoptimization of constraint satisfaction problems with approximation resistant predicates
• Parameterized dynamic variants of red-blue dominating set
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of max \(k\)-cover: approximation ratio threshold
• Solving continuous set covering problems by means of semi-infinite optimization. With an application in product portfolio optimization

This page was built for publication: Reoptimization of set covering problems

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