Search

In this paper, we present two nonmonotone versions of adaptive cubic regularized (ARC) method for unconstrained optimization problems. The proposed methods are a combination of the ARC algorithm with the nonmonotone line search methods introduced by Zhang and Hager [A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim. 14 (2004), pp. 1043–1056] and Ahookhosh et al. [A nonmonotone trust-region line search method for large-scale unconstrained optimization, Appl. Math. Model. 36 (2012), pp. 478–487]. The global convergence analysis for these iterative algorithms is established under suitable conditions. Several numerical examples are given to illustrate the efficiency and robustness of the newly suggested methods. The obtained results show the satisfactory performance of the proposed algorithms when compared to the basic ARC algorithm. [ABSTRACT FROM AUTHOR]

We extend the Mobile Server problem introduced in Feldkord and Meyer auf der Heide (TOPC 6(3), 14:1–14:17 2019) to a model where k identical mobile resources, here named servers, answer requests appearing at points in the Euclidean space. To reduce communication costs, the positions of the servers can be adapted by a limited distance ms per round for each server. The costs are measured similarly to the classical Page Migration problem: i.e., answering a request induces costs proportional to the distance to the nearest server, and moving a server induces costs proportional to the distance multiplied with a weight D. We show that, in our model, no online algorithm can have a constant competitive ratio: i.e., one which is independent of the input length n, even if an augmented moving distance of (1 + δ)ms is allowed for the online algorithm. Therefore we investigate a restriction of the power of the adversary dictating the sequence of requests: We demand locality of requests: i.e., that consecutive requests come from points in the Euclidean space with distance bounded by some constant mc. We show constant lower bounds on the competitiveness in this setting (independent of n, but dependent on k, ms and mc). On the positive side, we present a deterministic online algorithm with bounded competitiveness when an augmented moving distance and locality of requests is assumed. Our algorithm simulates any given algorithm for the classical k-Page Migration problem as guidance for its servers and extends it by a greedy move of one server in every round. The resulting competitive ratio is polynomial in the number of servers k, the ratio between mc and ms, the inverse of the augmentation factor 1/δ and the competitive ratio of the simulated k-Page Migration algorithm. We also show how to directly adapt the Double Coverage algorithm (Chrobak et al. SIAM J. Discrete Math. 4(2), 172–181 11) for the k-Server problem to receive an algorithm with improved competitiveness on the line. [ABSTRACT FROM AUTHOR]

We present a deterministic (1+o(1))-approximation O(n1/2+o(1) + D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(√n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є-1logє-1)-approximation factor of Lenzen and Patt-Shamir's Õ(n1/2+є+D)-time algorithm [STOC 2013, pp. 381-390] within the same running time. (Throughout, we use Õ(.) to hide polylogarithmic factors in n.) Our running time matches the known time lower bound of Ω(√n/log n + D) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40-57]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the "hitting set argument" commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (no(1), o(1))-hop set of size n1+o(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434-446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375-382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153-162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation no(1)-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation no(1)-pass n1+o(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565-573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]. [ABSTRACT FROM AUTHOR]

The purpose of this note is to correct the statement of Theorem 1.1 in [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] which consider any dimension d ≥ 2, since the proof given fails in dimension d = 2. The gap in the proof is in Lemma 2.5 of [J. A. Barceló et al., SIAM J. Appl. Math., 78 (2018), pp. 2714--2736] where an estimate for the resolvent of the Laplace operator (Δ + k²)-1 in Rd is stated for k small and any dimension d ≥ 2. However, this estimate is only true for d ≥ 3. [ABSTRACT FROM AUTHOR]

We revisit the classic problem of estimating the moments of the degree distribution of an undirected simple graph. Consider an undirected simple graph G = (V,E) with n (nonisolated) vertices, and define (for s > 0) Ms =\sum v\in V ds v. Our aim is to estimate Ms within a multiplicative error of (1 +\varepsilon) (for a given approximation parameter\varepsilon > 0) in sublinear time. We consider the sparse-graph model that allows access to uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of s = 1 (the average degree), O\ast (\surd n) queries suffice for any constant\varepsilon [U. Feige, SIAM J. Comput., 35 (2006), pp. 964--984], [O. Goldreich and D. Ron, Random Structures Algorithms, 32 (2008), pp. 473--493]. (We use the O\ast notation to suppress dependencies in log n and 1/\varepsilon.) Gonen, Ron, and Shavitt [SIAM J. Discrete Math., 25 (2011), pp. 1365--1411] extended this result to all integral s > 0 by designing an algorithm that performs O\ast (n1 1/(s+1)) queries. (Strictly speaking, their algorithm approximates the number of star-subgraphs of a given size, but a slight modification gives an algorithm for moments.) We design a new, significantly simpler algorithm for this problem. In the worst case, it exactly matches the bounds of Gonen, Ron, and Shavitt and has a much simpler proof. More importantly, the running time of this algorithm is connected to the arboricity of G. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with arboricity at most\alpha, it has a query complexity of O\ast\bigl(n\cdot\alpha 1/s M 1/s s + min\bigl\{ m M 1/s s, m\cdot ns 1 Ms\bigr\}\bigr) which is always upper bounded by O\ast\bigl(n\alpha M 1/s s\bigr). Thus, for the class of constant-arboricity graphs (which includes, among others, all minor-closed families and preferential attachment graphs), we can estimate the average degree in O\ast (1) queries, and we can estimate the variance of the degree distribution in O\ast (\surd n) queries. This is a major improvement over the previous worst-case bounds. [ABSTRACT FROM AUTHOR]

We consider some non-smooth functions and investigate the numerical behavior of the Piecewise Linear Hompotopy (PLH) method ([Bozântan, A., An implementation of the piecewise-linear homotopy algorithm for the computation of fixed points, Creat. Math. Inform., 19 (2010), No. 2, 140-148] and [Bozântan, A. and Berinde, V., Applications of the PL homotopy algorithm for the computation of fixed points to unconstrained optimization problems, Creat. Math. Inform., 22 (2013), No. 1, 41-46]). We compare the PLH method with the BFGS with inexact line search, a quasi-Newton method, having some results reported in [Lewis, A. S. and Overton, M. L., Nonsmooth optimization via BFGS, submitted to SIAM J. Optimiz, (2009)]. For most of the considered cases, the characteristics of the PLH method are quite similar to the BFGS method, that is, the PLH method converges to local minimum values and the convergence rate seems to be linear with respect to the number of function evaluations, but we also identify some issues with the PLH method. [ABSTRACT FROM AUTHOR]

We give a #NC upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta and Ramachandran (SIAM J. Comput. 21:755-780, ). We also show that the problem is #NC hard. Our results show that the difference between #BWBP and #NC is captured exactly by the addition of a visible stack to a nondeterministic finite-state automaton. [ABSTRACT FROM AUTHOR]