Solving Robust Weighted Independent Set Problems on Trees and under Interval Uncertainty
Abstract: The maximum weighted independent set (MWIS) problem is important since it occurs in various applications, such as facility location, selection of non-overlapping time slots, labeling of digital maps, etc. However, in real-life situations, input parameters within those models are often loosely defined or subject to change. For such reasons, this paper studies robust variants of the MWIS problem. The study is restricted to cases where the involved graph is a tree. Uncertainty of vertex weights is represented by intervals. First, it is observed that the max–min variant of the problem can be solved in linear time. Next, as the most important original contribution, it is proved that the min–max regret variant is NP-hard. Finally, two mutually related approximation algorithms for the min–max regret variant are proposed. The first of them is already known, but adjusted to the considered situation, while the second one is completely new. Both algorithms are analyzed and evaluated experimentally.
Keywords: weighted graph / independent set / robust optimization / interval uncertainty / tree / complexity / approximation algorithm
Scifeed alert for new publicationsNever miss any articles matching your research from any publisher
- Get alerts for new papers matching your research
- Find out the new papers from selected authors
- Updated daily for 49'000+ journals and 6000+ publishers
- Define your Scifeed now
Click here to see the statistics on "Symmetry" .