More Like this

1. A Randomly Weighted Minimum Arborescence with a Random Cost Constraint

   https://doi.org/10.1287/moor.2021.1184  

   Frieze, Alan M.; Tkocz, Tomasz (May 2022, Mathematics of Operations Research)

   We study the minimum spanning arborescence problem on the complete digraph [Formula: see text], where an edge e has a weight W e and a cost C e , each of which is an independent uniform random variable U s , where [Formula: see text] and U is uniform [Formula: see text]. There is also a constraint that the spanning arborescence T must satisfy [Formula: see text]. We establish, for a range of values for [Formula: see text], the asymptotic value of the optimum weight via the consideration of a dual problem. 

   more » « less
2. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra; Inamdar, Tanmay; Quanrud, Kent; Varadarajan, Kasturi; Zhang, Zhao (June 2022, Journal of Combinatorial Optimization)

   Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$ $f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$ $k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$ $S\subseteq N$such that$$f_i(S) \ge k_i$$ $f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$ $1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$ $O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$ $k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$ $(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$ $f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. 

   more » « less
3. Algorithms for Covering Barrier Points by Mobile Sensors with Line Constraint

   https://doi.org/10.1142/S0218195924500018  

   Jain, Princy; Wang, Haitao (February 2024, International Journal of Computational Geometry & Applications)

   We study the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range [Formula: see text] so that any point within distance [Formula: see text] from the sensor can be covered by the sensor. Given a set [Formula: see text] of [Formula: see text] points (called “barrier points”) and a set [Formula: see text] of [Formula: see text] points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this paper, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line [Formula: see text] and are required to move on [Formula: see text] only while the barrier points can be anywhere in the plane. We propose an [Formula: see text] time algorithm for the problem. We also consider the weighted case where each sensor has a weight; we give an [Formula: see text] time algorithm for this case. In the second problem, all barrier points are on [Formula: see text] while all sensors are in the plane but are required to move onto [Formula: see text] to cover all barrier points. We also solve the weighted case in [Formula: see text] time. 

   more » « less
4. Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems

   https://doi.org/10.1287/moor.2021.1181  

   Ghuge, Rohan; Nagarajan, Viswanath (May 2022, Mathematics of Operations Research)

   We consider the following general network design problem. The input is an asymmetric metric (V, c), root [Formula: see text], monotone submodular function [Formula: see text], and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time [Formula: see text]-approximation algorithm for this problem, in which [Formula: see text] is the number of vertices in an optimal solution. As a consequence, we obtain an [Formula: see text]-approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved [Formula: see text]-approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors). 

   more » « less
5. The Power of Subsampling in Submodular Maximization

   https://doi.org/10.1287/moor.2021.1172  

   Harshaw, Christopher; Kazemi, Ehsan; Feldman, Moran; Karbasi, Amin (January 2021, Mathematics of Operations Research)

   We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SampleGreedy, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-extendible system using [Formula: see text] evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and [Formula: see text] evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks. 

   more » « less