More Like this

1. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

   https://doi.org/10.4230/LIPIcs.ICALP.2020.30  

   Chen, Yu; Kannan, Sampath; Khanna, Sanjeev (April 2020, Leibniz international proceedings in informatics)

   We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))-time algorithm that returns a (1+epsilon)-approximate estimate of the MST cost. This result immediately implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)-time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)-approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an O^~(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2 − epsilon_0) for some epsilon_0 > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1, 2)-TSP where all distances are either 1 or 2, and give an O^~(n ^ 1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1, 2)-TSP naturally lend themselves to O^~(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1, 2)-TSP. These results motivate the natural question if analogously to metric MST, for any epsilon > 0, (1 + epsilon)-approximate estimates can be obtained for graphic TSP and (1, 2)-TSP using O^~ (n) queries. We answer this question in the negative – there exists an epsilon_0 > 0, such that any algorithm that estimates the cost of graphic TSP ((1, 2)-TSP) to within a (1 + epsilon_0)-factor, necessarily requires (n^2) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any epsilon > 0, any algorithm that estimates the cost of graphic TSP or (1, 2)-TSP to within a (1 + epsilon)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an epsilon n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation. 

   more » « less
2. Sensitivity of Distributed Optimization Convergence Performance to Reference Bus Location

   https://doi.org/10.1109/PESGM40551.2019.8973576  

   Mohammadi, A.; Safdarian, F.; Kargarian, A. (January 2020, 2019 IEEE Power & Energy Society General Meeting (PESGM))

   Distributed optimization is becoming popular to solve a large power system problem with the objective of reducing computational complexity. To this end, the convergence performance of distributed optimization plays an important role to solve an optimal power flow (OPF) problem. One of the critical factors that have a significant impact on the convergence performance is the reference bus location. Since selecting the reference bus location does not affect the result of centralized DC OPF, we can change the location of the reference bus to get more accurate results in distributed optimization. In this paper, our goal is to provide some insights into how to select reference bus location to have a better convergence performance. We modeled the power grid as a graph and based on some graph theory concepts, for each bus in the grid a score is assigned, and then we cluster buses to find out which buses are more suitable to be considered as the reference bus. We implement the analytical target cascading (ATC) on the IEEE 48-bus system to solve a DC OPF problem. The results show that by selecting a proper reference bus, we obtained more accurate results with an excellent convergence rate while improper selection may take much more iterations to converge. 

   more » « less
3. An Accelerated Asynchronous Distributed Method for Convex Constrained Optimization Problems

   https://doi.org/10.1109/CISS56502.2023.10089633  

   Abolfazli, Nazanin; Jalilzadeh, Afrooz; Hamedani, Erfan Yazdandoost (March 2023, 2023 57th Annual Conference on Information Sciences and Systems (CISS))

   We consider a class of multi-agent cooperative consensus optimization problems with local nonlinear convex constraints where only those agents connected by an edge can directly communicate, hence, the optimal consensus decision lies in the intersection of these private sets. We develop an asynchronous distributed accelerated primal-dual algorithm to solve the considered problem. The proposed scheme is the first asynchronous method with an optimal convergence guarantee for this class of problems, to the best of our knowledge. In particular, we provide an optimal convergence rate of $$\mathcal O(1/K)$$ for suboptimality, infeasibility, and consensus violation. 

   more » « less
4. Separating subadditive Euclidean functionals

   Frieze, A; Pegden, W (January 2017, Random structures & algorithms)

   The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form $$\beta \sqrt n$$ for the minimum length of a Traveling Salesperson Tour throuh $$n$$ random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such \emph{Euclidean functionals} on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through $$n$$ random points in $[0,1]^2$ was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential ($$e^{\tilde \Omega(n)}$$) time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms (a lower bound as strong as $$e^{\tilde \Omega (n)}$$ was not even been known in worst-case analysis). 

   more » « less
5. Global optimality in low-rank matrix optimization

   https://doi.org/10.1109/GlobalSIP.2017.8309166  

   Zhu, Zhihui; Li, Qiuwei; Tang, Gongguo; Wakin, Michael B. (November 2017, 2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP))

   This paper considers the minimization of a general objective function f (X) over the set of non-square n × m matrices where the optimal solution X* is low-rank. To reduce the computational burden, we factorize the variable X into a product of two smaller matrices and optimize over these two matrices instead of X. We analyze the global geometry for a general and yet well-conditioned objective function f (X) whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence. 

   more » « less