More Like this

1. Counting and Enumerating Optimum Cut Sets for Hypergraph k -Partitioning Problems for Fixed k

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

   Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang (December 2023, Mathematics of Operations Research)

   We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph [Formula: see text] with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts [Formula: see text]—known as a k-partition—so as to minimize an objective of interest. (1) If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. (2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an [Formula: see text]-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known [Formula: see text]-time deterministic algorithm, in which n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs). Funding: All authors were supported by NSF AF 1814613 and 1907937. 

   more » « less
2. Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design

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

   Nikolov, Aleksandar; Singh, Mohit; Tantipongpipat, Uthaipon (May 2022, Mathematics of Operations Research)

   We study optimal design problems in which the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector. We study the [Formula: see text]-optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. We introduce the proportional volume sampling algorithm to obtain nearly optimal bounds in the asymptotic regime when the number [Formula: see text] of measurements made is significantly larger than the dimension [Formula: see text] and obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements when [Formula: see text] is small. The algorithm also gives approximation guarantees for other optimal design objectives such as [Formula: see text]-optimality and the generalized ratio objective, matching or improving the previously best-known results. We further show that bounds similar to ours cannot be obtained for [Formula: see text]-optimal design and that [Formula: see text]-optimal design is NP-hard to approximate within a fixed constant when [Formula: see text]. 

   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. 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
5. Weighted Sobolev regularity and rate of approximation of the obstacle problem for the integral fractional Laplacian

   https://doi.org/10.1142/S021820251950057X  

   Borthagaray, Juan Pablo; Nochetto, Ricardo H.; Salgado, Abner J. (December 2019, Mathematical Models and Methods in Applied Sciences)

   We obtain regularity results in weighted Sobolev spaces for the solution of the obstacle problem for the integral fractional Laplacian [Formula: see text] in a Lipschitz bounded domain [Formula: see text] satisfying the exterior ball condition. The weight is a power of the distance to the boundary [Formula: see text] of [Formula: see text] that accounts for the singular boundary behavior of the solution for any [Formula: see text]. These bounds then serve us as a guide in the design and analysis of a finite element scheme over graded meshes for any dimension [Formula: see text], which is optimal for [Formula: see text]. 

   more » « less