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. Edge-Cuts of Optimal Average Weights

   https://doi.org/10.1142/S0217595919400062  

   Payne, Scott ; Fuller, Edgar ; Zhang, Cun-Quan ( April 2019 , Asia-Pacific Journal of Operational Research)

   Let [Formula: see text] be a directed graph associated with a weight [Formula: see text]. For an edge-cut [Formula: see text] of [Formula: see text], the average weight of [Formula: see text] is denoted and defined as [Formula: see text]. An optimal edge-cut with average weight is an edge-cut [Formula: see text] such that [Formula: see text] is maximum among all edge-cuts (or minimum, symmetrically). In this paper, a polynomial algorithm for this problem is proposed for finding an optimal edge-cut in a rooted tree separating the root and the set of all leafs. This algorithm enables us to develop an automatic clustering method with more accurate detection of community output. 

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