On approximating partial scenario set cover
References
[1]
O.D. Balalau, F. Bonchi, T.H.H. Chan, F. Gullo, M. Sozio, Finding subgraphs with maximum total density and limited overlap, in: Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, ACM, 2015, https://doi.org/10.1145/2684822.2685298.
[2]
R. Bar-Yehuda, Using homogeneous weights for approximating the partial cover problem, J. Algorithms 39 (2001) 137–144,.
[3]
R. Bar-Yehuda, S. Even, A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem, Elsevier, 1985, pp. 27–45. https://doi.org/10.1016/s0304-0208(08)73101-3.
[4]
A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, A. Vijayaraghavan, Detecting high log-densities: an o ( n 1 4 ) approximation for densest k-subgraph, in: Proceedings of the forty-second ACM symposium on Theory of computing, ACM, 2010, https://doi.org/10.1145/1806689.1806719.
[5]
M. Charikar, Greedy Approximation Algorithms for Finding Dense Components in a Graph, Springer, Berlin Heidelberg, 2000, pp. 84–95. https://doi.org/10.1007/3-540-44436-x_10.
[6]
C. Chekuri, G. Even, A. Gupta, D. Segev, Set connectivity problems in undirected graphs and the directed steiner network problem, ACM Trans. Algorithms 7 (2011) 1–17,.
[7]
C. Chekuri, T. Inamdar, K. Quanrud, K. Varadarajan, Z. Zhang, Algorithms for covering multiple submodular constraints and applications, J. Comb. Optim. 44 (2022) 979–1010,.
[8]
H. Chen, G. Loukides, R. Gwadera, S.P. Pissis, Heavy Nodes in a Small Neighborhood: Algorithms and Applications, Society for Industrial and Applied Mathematics, 2023, pp. 307–315. https://doi.org/10.1137/1.9781611977653.ch35.
[9]
E. Chlamtac, M. Dinitz, R. Krauthgamer, Everywhere-sparse spanners via dense subgraphs, in: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, https://doi.org/10.1109/focs.2012.61.
[10]
E. Chlamtáč, M. Dinitz, C. Konrad, G. Kortsarz, G. Rabanca, The densest k-subhypergraph problem, SIAM J. Discrete Math. 32 (2018) 1458–1477,.
[11]
E. Chlamtáč, M. Dinitz, Y. Makarychev, Minimizing the union: Tight approximations for small set bipartite vertex expansion, in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2017, https://doi.org/10.1137/1.9781611974782.56.
[12]
V. Chvatal, A greedy heuristic for the set-covering problem, Math. Oper. Res. 4 (1979) 233–235,.
[13]
I. Dinur, D. Steurer, Analytical approach to parallel repetition, in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM, 2014, pp. 624–633. https://doi.org/10.1145/2591796.2591884.
[14]
G. Dobson, Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Math. Oper. Res. 7 (1982) 515–531,.
[15]
U. Feige, A threshold of ln n for approximating set cover, J. ACM 45 (1998) 634–652,.
[16]
R. Gandhi, S. Khuller, A. Srinivasan, Approximation algorithms for partial covering problems, J. Algorithms 53 (2004) 55–84,.
[17]
A.V. Goldberg, Finding a Maximum Density Subgraph, Technical Report. USA 1984.
[18]
Goyal, V.; Ravi, R. (2008): Approximation Algorithms for Robust Covering Problems with Chance Constraints. Tepper WP, E17 https://doi.org/10.1184/R1/6703889.v1.
[19]
D.S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM J. Comput. 11 (1982) 555–556,.
[20]
D.H. Huang, A. Kahng, When clusters meet partitions: new density-based methods for circuit decomposition, in: Proceedings the European Design and Test Conference, ED&, TC 1995, IEEE Comput. Soc. Press, 1995,.
[21]
T. Inamdar, K. Varadarajan, On partial covering for geometric set systems, in: 34th International Symposium on Computational Geometry (SoCG 2018), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018.
[22]
S. Khuller, B. Saha, On Finding Dense Subgraphs, Springer, Berlin Heidelberg, 2009, pp. 597–608. https://doi.org/10.1007/978-3-642-02927-1_50.
[23]
S.O. Krumke, On the approximability of location and network design problems, Citeseer (1997).
[24]
S.O. Krumke, E. Schmidt, M. Streicher, Robust multicovers with budgeted uncertainty, Eur. J. Oper. Res. 274 (2019) 845–857,.
[25]
N. Megiddo, Combinatorial optimization with rational objective functions, Math. Oper. Res. 4 (1979) 414–424.
[26]
N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, J. ACM 30 (1983) 852–865.
[27]
C.H. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci. 43 (1991) 425–440,.
[28]
Ran, Y.; Zhang, Z. (2023): Approximation algorithm for minimum p union under a geometric setting. https://doi.org/10.2139/ssrn.4633820.
[29]
Y. Ran, Z. Zhang, S. Tang, D.Z. Du, Breaking the r max barrier: Enhanced approximation algorithms for partial set multicover problem, INFORMS J. Comput. 33 (2021) 774–784,.
[30]
Y. Shi, Y. Ran, Z. Zhang, J. Willson, G. Tong, D.Z. Du, Approximation algorithm for the partial set multi-cover problem, J. Glob. Optim. 75 (2019) 1133–1146,.
[31]
P. Slavík, Improved performance of the greedy algorithm for partial cover, Inf. Process. Lett. 64 (1997) 251–254,.
[32]
S. Toledo, Maximizing non-linear concave functions in fixed dimension, in: Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science, 1992, pp. 676–685.
[33]
V.V. Vazirani, Approximation Algorithms, Springer, Berlin Heidelberg, 2003, https://doi.org/10.1007/978-3-662-04565-7.
[34]
D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, https://doi.org/10.1017/cbo9780511921735.
[35]
P. Zhang, The lp-rounding plus greed approach for partial optimization revisited, Front. Comput. Sci. 16 (2022) 1–9,.
Index Terms
- On approximating partial scenario set cover
Index terms have been assigned to the content through auto-classification.
Recommendations
Approximation algorithms for minimum weight partial connected set cover problem
In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set $$U$$U, an integer $$q\le |U|$$q≤|U|, a collection $$\mathcal {E}$$E of subsets of $$U$$U, and a connected graph $$G_{\mathcal {E}}$$GE on vertex set $$\mathcal {...
Partially Polynomial Kernels for Set Cover and Test Cover
An instance of the $(n-k)$-Set Cover or the $(n-k)$-Test Cover problems is of the form $(\mathcal{U},\mathcal{S},k)$, where $\mathcal{U}$ is a set with $n$ elements, $\mathcal{S}\subseteq 2^\mathcal{U}$ with $|\mathcal{S}|=m$, and $k$ is the parameter. The ...
Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
In the unweighted set cover problem we are given a set of elements $E=\{e_1,e_2,\ldots,e_n\}$ and a collection ${\cal F}$ of subsets of $E$. The problem is to compute a subcollection $SOL\subseteq{\cal F}$ such that $\bigcup_{S_j\in SOL}S_j=E$ and its ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
The Author(s).
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 01 January 2025
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025