More Like this

1. A New Algorithm for Euclidean Shortest Paths in the Plane

   https://doi.org/10.1145/3580475  

   Wang, Haitao (April 2023, Journal of the ACM)

   Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri (in SIAM Journal on Computing , 1999) gave an algorithm of O(n log n ) time and O(n log n ) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space to O(n) while the runtime of the algorithm is still O(n log n ). In this article, we present a new algorithm of O(n+h log h ) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. The algorithm is better than the previous work when h is relatively small. Our algorithm builds a shortest path map for a source point s so that given any query point t , the shortest path length from s to t can be computed in O (log n ) time and a shortest s - t path can be produced in additional time linear in the number of edges of the path. 

   more » « less
2. The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem

   https://doi.org/10.1287/opre.2018.1839  

   Hochbaum, Dorit S.; Rao, Xu (September 2019, Operations Research)

   The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NP-hard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NP-hard for constant joint cycle length and prove that it is strongly NP-hard for nonconstant joint cycle length. For constant joint cycle-length discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the single-cycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NP-hard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multi-cycle RSP (with either constant or nonconstant cycle length) and the single-cycle RSP with constant cycle length and widen the gap for single-cycle RSP with nonconstant cycle length. For the multi-cycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NP-hard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multi-cycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NP-hard. 

   more » « less
3. Search-To-Decision Reductions for Kolmogorov Complexity

   https://doi.org/10.4230/lipics.ccc.2024.34  

   Mazor, Noam; Pass, Rafael (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   {"Abstract":["A long-standing open problem dating back to the 1960s is whether there exists a search-to-decision reduction for the time-bounded Kolmogorov complexity problem - that is, the problem of determining whether the length of the shortest time-t program generating a given string x is at most s.\r\nIn this work, we consider the more "robust" version of the time-bounded Kolmogorov complexity problem, referred to as the GapMINKT problem, where given a size bound s and a running time bound t, the goal is to determine whether there exists a poly(t,|x|)-time program of length s+O(log |x|) that generates x. We present the first non-trivial search-to-decision reduction R for the GapMINKT problem; R has a running-time bound of 2^{ε n} for any ε > 0 and additionally only queries its oracle on "thresholds" s of size s+O(log |x|). As such, we get that any algorithm with running-time (resp. circuit size) 2^{α s} poly(|x|,t,s) for solving GapMINKT (given an instance (x,t,s), yields an algorithm for finding a witness with running-time (resp. circuit size) 2^{(α+ε) s} poly(|x|,t,s).\r\nOur second result is a polynomial-time search-to-decision reduction for the time-bounded Kolmogorov complexity problem in the average-case regime. Such a reduction was recently shown by Liu and Pass (FOCS'20), heavily relying on cryptographic techniques. Our reduction is more direct and additionally has the advantage of being length-preserving, and as such also applies in the exponential time/size regime.\r\nA central component in both of these results is the use of Kolmogorov and Levin’s Symmetry of Information Theorem."]} 

   more » « less
4. Elastic Solution of a Polygon-Shaped Inclusion With a Polynomial Eigenstrain

   https://doi.org/10.1115/1.4050279  

   Wu, Chunlin; Yin, Huiming (June 2021, Journal of Applied Mechanics)

   null (Ed.)

   Abstract This paper presents the Eshelby’s tensor of a polygonal inclusion with a polynomial eigenstrain, which can provide an elastic solution to an arbitrary, convex inclusion with a continuously distributed eigenstrain by the Taylor series approximation. The Eshelby’s tensor for plane strain problem is derived from the fundamental solution of isotropic Green’s function with the Hadmard regularization, which is composed of the integrals of the derivatives of the harmonic and biharmonic potentials over the source domain. Using the Green’s theorem, they are converted to two line (contour) integrals over the polygonal cross section. This paper evaluates them by direct analytical integrals. Following Mura’s work, this paper formulates the method to derive linear, quadratic, and higher order of the Eshelby’s tensor in the polynomial form for arbitrary, convex polygonal shapes of inclusions. Numerical case studies were performed to verify the analytic results with the original Eshelby’s solution for a uniform eigenstrain in an ellipsoidal domain. It is of significance to consider higher order terms of eigenstrain for the polygon-shape inclusion problem because the eigenstrain distribution is generally non-uniform when Eshelby’s equivalent inclusion method is used. The stress disturbance due to a triangle particle in an infinite domain is demonstrated by comparison with the results of the finite element method (FEM). The present solution paves the way to accurately simulate the particle-particle, partial-boundary interactions of polygon-shape particles. 

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