More Like this

1. A Randomly Weighted Minimum Spanning Tree with a Random Cost Constraint

   https://doi.org/10.37236/9445  

   Frieze, Alan; Tkocz, Tomasz (January 2021, The Electronic Journal of Combinatorics)

   We study the minimum spanning tree problem on the complete graph $$K_n$$ where an edge $$e$$ has a weight $$W_e$$ and a cost $$C_e$$, each of which is an independent copy of the random variable $$U^\gamma$$ where $$\gamma\leq 1$$ and $$U$$ is  the uniform $[0,1]$ random variable. There is also a constraint that the spanning tree $$T$$ must satisfy $$C(T)\leq c_0$$. We establish, for a range of values for $$c_0,\gamma$$, the asymptotic value of the optimum weight via the consideration of a dual problem. 

   more » « less
2. Breaking the r _max Barrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

   https://doi.org/10.1287/ijoc.2020.0975  

   Ran, Yingli; Zhang, Zhao; Tang, Shaojie; Du, Ding-Zhu (October 2020, INFORMS Journal on Computing)

   null (Ed.)

   Given an element set E of order n, a collection of subsets [Formula: see text], a cost c S on each set [Formula: see text], a covering requirement r e for each element [Formula: see text], and an integer k, the goal of a minimum partial set multicover problem (MinPSMC) is to find a subcollection [Formula: see text] to fully cover at least k elements such that the cost of [Formula: see text] is as small as possible and element e is fully covered by [Formula: see text] if it belongs to at least r e sets of [Formula: see text]. This problem generalizes the minimum k-union problem (MinkU) and is believed not to admit a subpolynomial approximation ratio. In this paper, we present a [Formula: see text]-approximation algorithm for MinPSMC, in which [Formula: see text] is the maximum size of a set in S. And when [Formula: see text], we present a bicriteria algorithm fully covering at least [Formula: see text] elements with approximation ratio [Formula: see text], where [Formula: see text] is a fixed number. These results are obtained by studying the minimum density subcollection problem with (or without) cardinality constraint, which might be of interest by itself. 

   more » « less
3. 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
4. A trace inequality of Ando, Hiai, and Okubo and a monotonicity property of the Golden–Thompson inequality

   https://doi.org/10.1063/5.0091111  

   Carlen, Eric A.; Lieb, Elliott H. (June 2022, Journal of Mathematical Physics)

   The Golden–Thompson trace inequality, which states that Tr  e H+ K ≤ Tr  e H e K , has proved to be very useful in quantum statistical mechanics. Golden used it to show that the classical free energy is less than the quantum one. Here, we make this G–T inequality more explicit by proving that for some operators, notably the operators of interest in quantum mechanics, H = Δ or [Formula: see text] and K = potential, Tr  e H+(1− u) K e uK is a monotone increasing function of the parameter u for 0 ≤ u ≤ 1. Our proof utilizes an inequality of Ando, Hiai, and Okubo (AHO): Tr  X s Y t X 1− s Y 1− t ≤ Tr  XY for positive operators X, Y and for [Formula: see text], and [Formula: see text]. The obvious conjecture that this inequality should hold up to s + t ≤ 1 was proved false by Plevnik [Indian J. Pure Appl. Math. 47, 491–500 (2016)]. We give a different proof of AHO and also give more counterexamples in the [Formula: see text] range. More importantly, we show that the inequality conjectured in AHO does indeed hold in the full range if X, Y have a certain positivity property—one that does hold for quantum mechanical operators, thus enabling us to prove our G–T monotonicity theorem. 

   more » « less
5. 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