Search

In the Bin Packing problem one is given n items with weights w(1),. . . ,w(n) and m bins with capacities c1, . . ., cm. The goal is to partition the items into sets S1, . . . ,Sm such that w(Sjmn) notation omits factors polynomial in the input size). In this paper, we show that for every m N there exists a constant Σm > 0 such that an instance of Bin Packing with m bins can be solved in O (2(1 y m)n) randomized time. Before our work, such improved algorithms were not known even for m= 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset Σ: For every γ > 0 there exists an >0 such that if | { X n{ 1, . . . ,n}: w(X) =v} | 2(1)n for some v, then { w(X) :X { 1, . . . ,n\} | &#947n. [ABSTRACT FROM AUTHOR]

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] for packing/covering linear programs. [ABSTRACT FROM AUTHOR]

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678--708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777--800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(n-A · MF(/cn,m T/c2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(nz,mz) is the time complexity of a max-flow algorithm in a network with nz nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovasz-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem. [ABSTRACT FROM AUTHOR]

Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of ℓ1 and ℓ2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing ℓ1/ℓ2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka--Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the ℓ1/ℓ2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell 2 norm or Lorentzian norm via solving the corresponding ℓ1/ℓ2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy. [ABSTRACT FROM AUTHOR]

This paper proposes some efficient and accurate adaptive two-grid (ATG) finite element algorithms for linear and nonlinear PDEs. The main idea of these algorithms is to utilize the solutions on the kth-level adaptive meshes to find the solutions on the (k + 1)th-level adaptive meshes which are constructed by performing adaptive element bisections on the k th-level adaptive meshes. These algorithms transform nonsymmetric positive definite (non-SPD) PDEs (resp., nonlinear PDEs) into symmetric positive definite (SPD) PDEs (resp., linear PDEs). The proposed algorithms are both accurate and efficient due to the following advantages: They do not need to solve the nonsymmetric or nonlinear systems; the degrees of freedom are very small, they are easily implemented, and the interpolation errors are very small. Next, this paper constructs residual-type a posteriori error estimators which are shown to be reliable and efficient. The key ingredient in proving the efficiency is to establish an upper bound of the oscillation terms, which may not be higher-order terms due to the low regularity of the numerical solution. Furthermore, the convergence of the algorithms is proved when bisection is used for the mesh refinements. Finally, numerical experiments are provided to verify the accuracy and efficiency of the ATG finite element algorithms compared to regular adaptive finite element algorithms and two-grid finite element algorithms [J. Xu, SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777]. [ABSTRACT FROM AUTHOR]

In this paper, we resolve the one-pass space complexity of perfect Lp sampling for p ∈ (0, 2) in a stream. Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ ℝn, a perfect Lp sampler must output an index i with probability |fi|p/∥ f∥pp and is allowed to fail with some probability δ. So far, for p > 0 no algorithm has been shown to solve the problem exactly using poly(log n)-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate Lp sampler which, given an approximation parameter ν, outputs i with probability (1±ν)|fi| p/∥f∥pp, using space polynomial in ν-1 and log(n). The space complexity was later reduced by Jowhari, Sağlam, and Tardos to roughly O(ν-p log² n log δ-1) for p ∈ (0, 2), which matches the general p ≥ 0 lower bound of Ω (log² n log δ-1) in terms of n and δ, but is loose in terms of ν. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of ν---not even a bound of Ω (ν-1) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log² n log δ-1)-bit perfect Lp sampler for p ∈ (0, 2). This shows that ν need not factor into the space of an Lp sampler, which closes the complexity of the problem for this range of p. For p = 2, our bound is O(log³ n log δ-1)-bits, which matches the prior best known upper bound of O(ν-2 log³ n log δ-1), but has no dependence on ν. Note that there is still a log n gap between our upper bound and the lower bound for p = 2, the ution of which we leave as an open problem. For p < 2, our bound holds in the random oracle model, matching the lower bounds in that model. However, we show that our algorithm can be derandomized with only a O((log log n)²) blow-up in the space (and no blow-up for p = 2). Our derandomization technique is quite general, and can be used to derandomize a large class of linear sketches, including the more accurate count-sketch variant of Minton and Price [Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 669-686], resolving an open question in that paper. Finally, we show that a (1 ± ∈) relative error estimate of the frequency fi of the sampled index i can be obtained using an additional O(∈-p log n)-bits of space for p < 2, and O(∈-2 log² n) bits for p = 2, which was possible before only by running the prior algorithms with ν = ∈. [ABSTRACT FROM AUTHOR]

In this paper, we study smooth stochastic multilevel composition optimization problems, where the objective function is a nested composition of T functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze their convergence to an e-stationary point of the problem. We show that the first algorithm, which is a generalization of [S. Ghadimi, A. Ruszczynski, and M. Wang, SIAM J. Optim., 30 (2020), pp. 960-979] to the T level case, can achieve a sample complexity of OT(1/ε6) by using minibatches of samples in each iteration, where OT hides constants that depend on T. By modifying this algorithm using linearized stochastic estimates of the function values, we improve the sample complexity to OT(1/ε4). This modification not only removes the requirement of having a minibatch of samples in each iteration, but also makes the algorithm parameter-free and easy to implement. To the best of our knowledge, this is the first time that such an online algorithm designed for the (un)constrained multilevel setting obtains the same sample complexity of the smooth single-level setting, under standard assumptions (unbiasedness and boundedness of the second moments) on the stochastic first-order oracle. [ABSTRACT FROM AUTHOR]

Dynamical low-rank algorithms are a class of numerical methods that compute lowrank approximations of dynamical systems. This is accomplished by projecting the dynamics onto a low-dimensional manifold and writing the solution directly in terms of the low-rank factors. The approach has been successfully applied to many types of differential equations. Recently, efficient dynamical low-rank algorithms have been proposed in [L. Einkemmer, A Low-Rank Algorithm for Weakly Compressible Flow, arXiv:1804.04561, 2018; L. Einkemmer and C. Lubich, SIAM J. Sci. Comput., 40 (2018), pp. B1330-B1360] to treat kinetic equations, including the Vlasov-Poisson and the Boltzmann equation. There it was demonstrated that the methods are able to capture the lowrank structure of the solution and significantly reduce numerical cost, while often maintaining high accuracy. However, no numerical analysis is currently available. In this paper, we perform an error analysis for a dynamical low-rank algorithm applied to the multiscale linear Boltzmann equation (a classical model in kinetic theory) to showcase the validity of the application of dynamical lowrank algorithms to kinetic theory. The equation, in its parabolic regime, is known to be rank 1 theoretically, and we will prove that the scheme can dynamically and automatically capture this low-rank structure. This work thus serves as the first mathematical error analysis for a dynamical low-rank approximation applied to a kinetic problem. [ABSTRACT FROM AUTHOR]

The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as CSPs of bounded width) was proposed by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57104]. It was confirmed by two independent proofs by Bulatov [Bounded Relational Width, manuscript, 2009] and Barto and Kozik [L. Barto and M. Kozik, 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 595 603], [L. Barto and M. Kozik, J. ACM, 61 (2014), 3]. Later Barto [J. Logic Comput., 26 (2014), pp. 923 943] proved a collapse of the hierarchy of local consistency notions by showing that (2; 3) minimality solves all the CSPs of bounded width. In this paper we present a new consistency notion, jpq consistency, which also solves all the CSPs of bounded width. Our notion is strictly weaker than (2; 3) consistency, (2; 3) minimality, path consistency, and singleton arc consistency (SAC). This last fact allows us to answer the question of Chen, Dalmau, and Gruien [J. Logic Comput., 23 (2013), pp. 87 108] by confirming that SAC solves all the CSPs of bounded width. Moreover, as known algorithms work faster for SAC, the result implies that CSPs of bounded width can be, in practice, solved more efficiently. The definition of jpq consistency is closely related to a consistency condition obtained from the rounding of an SDP relaxation of a CSP instance. In fact, the main result of this paper is used by Dalmau et al. [Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, ACM, New York, 2017, pp. 340{357] to show that CSPs with near unanimity polymorphisms admit robust approximation algorithms with polynomial loss. Finally, an algebraic characterization of some term conditions satisfied in algebras associated with templates of bounded width, first proved by Brady, is a direct consequence of our result. [ABSTRACT FROM AUTHOR]

We consider a classical k-center problem in trees. Let T be a tree of n vertices such that every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir [SIAM J. Comput., 12 (1983), pp. 751-758] gave an algorithm that can solve the problem in O(n log²n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

Reduced model spaces, such as reduced bases and polynomial chaos, are linear spaces Vn of finite dimension n which are designed for the efficient approximation of certain families of parametrized PDEs in a Hilbert space V. The manifold M that gathers the solutions of the PDE for all admissible parameter values is globally approximated by the space Vn with some controlled accuracy εn, which is typically much smaller than when using standard approximation spaces of the same dimension such as finite elements. Reduced model spaces have also been proposed in [Y. Maday et al., Internat. J. Numer. Methods Ergrg., 102 (2015), pp. 933-965] as a vehicle to design a simple linear recovery algorithm of the state u ∈ M corresponding to a particular solution instance when the values of parameters are unknown but a set of data is given by m linear measurements of the state. The measurements are of the form ℓj(u), j = 1, ..., m, where the ℓj are linear functionals on V. The analysis of this approach in [P. Binev et al., SIAM/ASA J. Uncertain. Quantif., 5 (2017), pp. 1-29] shows that the recovery error is bounded by μnεn, where μn = μ(Vn, W) is the inverse of an inf-sup constant that describe the angle between Vn and the space W spanned by the Riesz representers of (ℓ1, ..., ℓm). A reduced model space which is efficient for approximation might thus be ineffective for recovery if μn is large or infinite. In this paper, we discuss the existence and effective construction of an optimal reduced model space for this recovery method. We extend our search to affine spaces which are better adapted than linear spaces for various purposes. Our basic observation is that this problem is equivalent to the search of an optimal affine algorithm for the recovery of M in the worst case error sense. This allows us to perform our search by a convex optimization procedure. Numerical tests illustrate that the reduced model spaces constructed from our approach perform better than the classical reduced basis spaces. [ABSTRACT FROM AUTHOR]

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. [ABSTRACT FROM AUTHOR]

We study the iteration complexity of the optimistic gradient descent-ascent (OGDA) method and the extragradient (EG) method for finding a saddle point of a convex-concave unconstrained min-max problem. To do so, we first show that both OGDA and EG can be interpreted as approximate variants of the proximal point method. This is similar to the approach taken in (A. Nemirovski (2004), SIAM J. Optim., 15, pp. 229-251) which analyzes EG as an approximation of the "conceptual mirror prox." In this paper, we highlight how gradients used in OGDA and EG try to approximate the gradient of the proximal point method. We then exploit this interpretation to show that both algorithms produce iterates that remain within a bounded set. We further show that the primal-dual gap of the averaged iterates generated by both of these algorithms converge with a rate of O(1/k). Our theoretical analysis is of interest as it provides the first convergence rate estimate for OGDA in the general convex-concave setting. Moreover, it provides a simple convergence analysis for the EG algorithm in terms of function value without using a compactness assumption. [ABSTRACT FROM AUTHOR]

The Strang splitting method, formally of order two, can suffer from order reduction when applied to semilinear parabolic problems with inhomogeneous boundary conditions. The recent work [L. Einkemmer and A. Ostermann, SIAM J. Sci. Comput., 37, 2015; SIAM J. Sci. Comput., 38, 2016] introduces a modification of the method to avoid the reduction of order based on the nonlinearity. In this paper we introduce a new correction constructed directly from the flow of the nonlinearity and which requires no evaluation of the source term or its derivatives. The goal is twofold. One, this new modification requires only one evaluation of the diffusion flow and one evaluation of the source term flow at each step of the algorithm and it reduces the computational effort to construct the correction. Second, numerical experiments suggest it is well suited in the case where the nonlinearity is stiff. We provide a convergence analysis of the method for a smooth nonlinearity and perform numerical experiments to illustrate the performances of the new approach. [ABSTRACT FROM AUTHOR]

In this paper we study the orthogonal low-rank approximation problem of tensors in the general setting in the sense that more than one matrix factor is required to be mutually orthonormal, which includes the completely orthogonal low-rank approximation and semiorthogonal low-rank approximation as two special cases. It has been addressed in [L. Wang and M. T. Chu, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1058--1072] that "the question of more than one semiorthogonal factor matrix, except for the case of complete orthogonality, remains open." To deal with this open question we present an SVD-based algorithm. Our SVD-based algorithm updates two vectors simultaneously and maintains the required orthogonality conditions by means of the polar decomposition. The convergence behavior of our algorithm is analyzed for both objective function and iterates themselves and is illustrated by numerical experiments. [ABSTRACT FROM AUTHOR]

The classical convergence analysis of quasi-Newton methods assumes that function and gradient evaluations are exact. In this paper, we consider the case when there are (bounded) errors in both computations and establish conditions under which a slight modification of the BFGS algorithm with an Armijo–Wolfe line search converges to a neighborhood of the solution that is determined by the size of the errors. One of our results is an extension of the analysis presented in [R. H. Byrd and J. Nocedal, SIAM J. Numer. Anal., 26 (1989), pp. 727–739], which establishes that, for strongly convex functions, a fraction of the BFGS iterates are good iterates. We present numerical results illustrating the performance of the new BFGS method in the presence of noise. [ABSTRACT FROM AUTHOR]

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n1-1/O(q² log{l}o}{g}² q) sample complexity, following the definition of Goldreich and Ron [ACM Trans. Comput. Theory, 8 (2016), 7]. We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacypreserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish [SIAM J. Comput., 50 (2021), pp. 788--813]. We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev [Proceedings of the 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1163--1182], bypassing an exponential blowup caused by previous techniques in the case of adaptive testers. We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum [Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017, pp. 39:1--39:43; Comput. Complexity, 27 (2018), pp. 99-207] regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal--Szemeedi theorem. [ABSTRACT FROM AUTHOR]

For a fixed finite collection of graphs F, the F-M-DELETION problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time fF(tw) - n°(1), where tw is the treewidth of G for some function ƒ depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function ff. Here we provide an algorithm showing that fF(tw) = 2° (tw.log tw) for every collection F. Prior to this work, the best known function ƒ was double- exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K5, K3,3} and of Kociumaka and Pilipczuk [Algorithmica, 81 (2019), pp. 3655-3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inform. Comput., 256 (2017), pp. 62-82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections F [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135-152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56-77], our algorithm yields the following complexity dichotomy when F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: ƒH(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and fH(tw) = 2Θ(tw-log tw) otherwise. [ABSTRACT FROM AUTHOR]

Given an undirected n-vertex graph and k pairs (si,ti),..,, (sfc,tfc) of terminal vertices, the fc-DlSJOINT SHORTEST PATHS (fc-SDP) problem asks whether there are k pairwise vertex-disjoint paths Pi,...,Pk such that Pi is a shortest s-ti-path for each i E [fc]. Recently, Lochet [Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21), SIAM, 2021, pp. 169-178] provided an algorithm that solves fc-SDP in no time, answering a 20-year old question about the computational complexity of fc-SDP for constant fc. On the one hand, we present an improved no-time algorithm based on a novel geometric view on this problem. For the special case fc = 2 on m-edge graphs, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a refined analysis. On the other hand, we show that fc-SDP is W[l]-hard with respect to fc, showing that the dependency of the degree of the polynomial running time on the parameter fc is presumably unavoidable. [ABSTRACT FROM AUTHOR]

We study the issue of strong convergence of inexact proximal point algorithms (introduced by Rockafellar in [SIAM J. Control Optim., 14 (1976), pp. 877-898]) for maximal monotone operators on Hilbert spaces. A unified global/local strong convergence of inexact proximal point algorithms is established under the Hölder metrically subregular condition. Furthermore, quantitative estimates on the convergence rate of inexact proximal point algorithms are also provided. Applying to the special case of the classical (exact) proximal point algorithm, our results improve the corresponding ones in [G. Li and B. S. Mordukhovich, SIAM J. Optim., 22 (2012), pp. 1655-1684]. Finally, as applications, global/local strong convergence and estimates on the convergence rate of inexact proximal point algorithms for optimization problems are presented. [ABSTRACT FROM AUTHOR]

In a two-player noncooperative game framework, we deal with the affine relaxations of the best response algorithm (where a player's strategy is a best response to the strategy of the other player that comes from the previous step), motivated by the first results obtained for convex relaxations in zero-sum games (J. Morgan, Int. J. Comput. Math., 4 (1974), pp. 143-175) and for nonconvex affine relaxations in non-zero-sum games (F. Caruso, M. C. Ceparano, and J. Morgan, SIAM J. Optim., 30 (2020), pp. 1638-1663). In order to be able to specify the convergence of any type of affine relaxation of the best response algorithm, we define a new class of games, called ratiobounded games. This class contains games broadly used in literature (such as weighted potential and zero-sum games), both in finite and infinite dimensional settings. Its definition relies on a unifying property and on three associate key parameters explicitly related to the data. Depending on how the parameters are ordered, we provide a classification of the ratio-bounded games in four subclasses such that, for each of them, the following issues are answered when the strategy sets are real Hilbert spaces: existence and uniqueness of the Nash equilibria, global convergence of the affine relaxations of the best response algorithm, estimation of the related errors, determination of the algorithm with the highest speed of convergence, and comparison with the known results. Moreover, the investigation is supplemented by illustrating numerical examples and by describing a black-box model with a first-order oracle for an implementation of the algorithm. [ABSTRACT FROM AUTHOR]

Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order L ≥1 sum to at most cl (dl(1 + log n)l-1, where n is the number of variables, d is the tree depth, and c> 0 is an absolute constant. This bound is essentially tight and settles a conjec-ture due to Tal [Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. The bounds prior to our work degraded rapidly with L becoming trivial already at L = Dd. As an application, we obtain, for every integer k ≥ 1, a partial Boolean function on n bits that has bounded-error quantum query complexity at most k and randomized - 1 query complexity ...(n1— 1/2k). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [SIAM J. Comput., 47 (2018), pp. 982-1038] and Bravyi et al. [Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: 0(1) versus Ω(n2/3-ε) for any e > 0 [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]. As another application, we obtain an essentially optimal separation of O(1) versus Ω(n1—ε) for bounded-error quantum versus randomized communication complexity for any e > 0. The best previous separation was polynomially weaker: O(logn) versus 52(n2/3-ε) (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query com-plexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228-239]). [ABSTRACT FROM AUTHOR]

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP+AIP algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs. [ABSTRACT FROM AUTHOR]

This work focuses on angular values of nonautonomous dynamical systems which have been introduced for general random and (non)autonomous dynamical systems in a previous publication [W.-J. Beyn, G. Froyland, and T. H\"uls, SIAM J. Appl. Dyn. Syst., 21 (2022), pp. 1245-1286]. The angular value of dimension s measures the maximal average rotation which an s-dimensional subspace of the phase space experiences through the dynamics of a discrete-time linear system. Our main results relate the notion of angular value to the well-known dichotomy (or Sacker--Sell) spectrum and its associated spectral bundles. In particular, we prove a reduction theorem which shows that instead of maximizing over all subspaces, it suffices to maximize over so-called trace spaces which have their basis in the spectral fibers. The reduction leads to an algorithm for computing angular values of dimensions one and two. We apply the algorithm to several systems of dimension up to 4 and demonstrate its efficiency to detect the fastest rotating subspace even if it is not dominant under the forward dynamics. [ABSTRACT FROM AUTHOR]

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that for every s \geq 1, both problems are polynomial-time solvable for sP3-free graphs and (sP1 + P5)-free graphs; here, the graph sP3 denotes the disjoint union of s paths on three vertices and the graph sP1 + P5 denotes the disjoint union of s isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on H-free graphs, namely for sP2-free graphs [Chiarelli et al., Theoret. Comput. Sci., 705 (2018), pp. 75--83], (sP1+P3)-free graphs [Dabrowski et al., Algorithmica, 82 (2020), pp. 2841--2866] and P5-free graphs [Abrishami et al., Induced subgraphs of bounded treewidth and the container method, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2021, pp. 1948--1964]. Together, the new results also show that both problems exhibit the same behavior on H-free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a (sP3)-free or (sP1 + P5)-free graph G a largest induced subgraph whose blocks belong to some finite class \scrC of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs. [ABSTRACT FROM AUTHOR]

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(√ k) instead of O(k) (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number k = |T| of terminals is regarded as the parameter. We show that Subset TSP can be solved in time 2O(√k log k) · nO(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014, SIAM, Philadelphia, 2014, pp. 1812-1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. [ABSTRACT FROM AUTHOR]

Computing a flow system a number of times with different samples of flow parameters is a common practice in many uncertainty quantification applications, which can be prohibitively expensive for complex nonlinear flow problems. This report presents two second order, stabilized, scalar auxiliary variable (SAV) ensemble algorithms for fast computation of the Navier--Stokes flow ensembles: Stab-SAV-CN and Stab-SAV-BDF2. The proposed ensemble algorithms are based on the ensemble timestepping idea which makes use of a quantity called the ensemble mean to construct a common coefficient matrix for all realizations at the same time step after spatial discretization, in which case efficient block solvers, e.g., block GMRES, can be used to significantly reduce both storage and computational time. The adoption of a recently developed SAV approach that treats the nonlinear term explicitly results in a constant shared coefficient matrix among all realizations at different time steps, which further cuts down the computational cost, yielding an extremely efficient ensemble algorithm for simulating nonlinear flow ensembles with provable long time stability without any time step conditions. The SAV approach for the Navier--Stokes equations for a single realization was proved to be unconditionally stable in [L. Lin, Z. Yang, and S. Dong, J. Comput. Phys., 388 (2019), pp 1-22; X. Li and J. Shen, SIAM J. Numer. Anal., 58 (2020), pp. 2465-2491]. However we found the SAV approach has very low accuracy that compromises its stability in our initial numerical investigations for several commonly tested benchmark flow problems. In this report, we propose to use the stabilization in Stab-SAV-BDF2 to address this issue. We prove that both of our ensemble algorithms are long time stable under one parameter fluctuation condition, without any time step constraints. For a single realization, both algorithms are unconditionally stable and have better accuracy than the SAV methods studied in [L. Lin, Z. Yang, and S. Dong, J. Comput. Phys., 388 (2019), pp 1-22; X. Li and J. Shen, SIAM J. Numer. Anal., 58 (2020), pp. 2465-2491] for our test problems. Extensive numerical experiments are performed to show the efficiency of the proposed ensemble algorithms and the effectiveness of the stabilization for increasing accuracy and stability. [ABSTRACT FROM AUTHOR]

This work is concerned with approximating a trivariate function defined on a tensorproduct domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations that can be computed and stored very efficiently. The existing Chebfun3 algorithm [B. Hashemi and L. N. Trefethen, SIAM J. Sci. Comput., 39 (2017), pp. C341--C363] uses a similar format, but the construction of the approximation proceeds indirectly, via a so-called slice-Tucker decomposition. As a consequence, Chebfun3 sometimes unnecessarily uses many function evaluations and does not fully benefit from the potential of the Tucker decomposition to reduce, sometimes dramatically, the computational cost. We propose a novel algorithm Chebfun3F that utilizes univariate fibers instead of bivariate slices to construct the Tucker decomposition. Chebfun3F reduces the cost for the approximation in terms of the number of function evaluations for nearly all functions considered, typically by 75\% and sometimes by over 98\%. [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]

We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ(nb²) time so that one can compute any additively weighted Voronoi diagram for these sites in Õ (b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ(n5/3) time. This improves the recent breakthrough result of Cabello [SODA 2017, SIAM, Philadelphia, 2017, pp. 2143{2152], both by improving the running time (from Õ(n11/6)), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex v, both the farthest vertex from v (i.e., the eccentricity of v), and the sum of distances from v to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds. Our construction of Voronoi diagrams for planar graphs is of independent interest. [ABSTRACT FROM AUTHOR]

We study the convergence issue for the gradient algorithm (employing general step sizes) for optimization problems on general Riemannian manifolds (without curvature constraints). Under the assumption of the local convexity/quasi-convexity (resp., weak sharp minima), local/global convergence (resp., linear convergence) results are established. As an application, the linear convergence properties of the gradient algorithm employing the constant step sizes and the Armijo step sizes for finding the Riemannian Lp (p ∈ [1, + ∞)) centers of mass are explored, respectively, which in particular extend and/or improve the corresponding results in [B. Afsari, R. Tron, and R. Vidal, SIAM J. Control Optim., 51 (2013), pp. 2230-2260; G. C. Bento et al., J. Optim. Theory Appl., 183 (2019), pp. 977-992]. [ABSTRACT FROM AUTHOR]

In recent years there has been an emerging interest in PDE-like ows defined on finite graphs, with applications in clustering and image segmentation. In particular for image segmentation and semisupervised learning Bertozzi and Flenner [Multiscale Model. Simul., 10 (2012), pp. 1090{1118] developed an algorithm based on the Allen{Cahn (AC) gradient ow of a graph Ginzburg{Landau functional, and Merkurjev, Kostic, and Bertozzi [SIAM J. Imaging Sci., 6 (2013), pp. 1903{1930] devised a variant algorithm based instead on graph Merriman{Bence{Osher (MBO) dynamics. This work offers rigorous justification for this use of the MBO scheme in place of AC ow. First, we choose the double-obstacle potential for the Ginzburg{Landau functional and derive wellposedness and regularity results for the resulting graph AC ow. Next, we exhibit a \semidiscrete" time-discretization scheme for AC ow of which the MBO scheme is a special case. We investigate the long-time behavior of this scheme and prove its convergence to the AC trajectory as the time-step vanishes. Finally, following a question raised by Van Gennip, Guillen, Osting, and Bertozzi [Milan J. Math., 82 (2014), pp. 3{65], we exhibit results toward proving a link between double-obstacle AC ow and mean curvature ow on graphs. We show some promising -convergence results and translate to the graph setting two comparison principles used by Chen and Elliott [Proc. Math. Phys. Sci., 444 (1994), pp. 429{445] to prove the analogous link in the continuum. [ABSTRACT FROM AUTHOR]

Explaining the excellent practical performance of the simplex method for linear programming has been a major topic of research for over 50 years. One of the most successful frameworks for understanding the simplex method was given by Spielman and Teng [J. ACM, 51 (2004), pp. 385--463] who developed the notion of smoothed analysis. Starting from an arbitrary linear program (LP) with d variables and n constraints, Spielman and Teng analyzed the expected runtime over random perturbations of the LP, known as the smoothed LP, where variance \sigma 2 Gaussian noise is added to the LP data. In particular, they gave a two-stage shadow vertex simplex algorithm which uses an expected \widetilde O(d55n86\sigma 30 + d70n86) number of simplex pivots to solve the smoothed LP. Their analysis and runtime was substantially improved by Deshpande and Spielman [FOCS '05, 2005, pp. 349--356] and later Vershynin [SIAM J. Comput., 39 (2009), pp. 646--678]. The fastest current algorithm, due to Vershynin, solves the smoothed LP using an expected O \bigl(log2 n \cdot log log n \cdot (d3\sigma 4+d5 log2 n+d9 log4 d) \bigr) number of pivots, improving the dependence on n from polynomial to polylogarithmic. While the original proof of Spielman and Teng has now been substantially simplified, the resulting analyses are still quite long and complex and the parameter dependencies far from optimal. In this work, we make substantial progress on this front, providing an improved and simpler analysis of shadow simplex methods, where our algorithm requires an expected O(d2 \surd log n \sigma 2 + d3 log3/2 n) number of simplex pivots. We obtain our results via an improved shadow bound, key to earlier analyses as well, combined with improvements on algorithmic techniques of Vershynin. As an added bonus, our analysis is completely modular and applies to a range of perturbations, which, aside from Gaussians, also includes Laplace perturbations. [ABSTRACT FROM AUTHOR]

We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures [B. Allen and I. Munro, J. ACM, 25 (1978), pp. 526{535; D. D. Sleator and R. E. Tarjan, J. ACM, 32 (1985), pp. 652{686; M. L. Fredman et al., Algorithmica, 1 (1986), pp. 111{129; R. Wilber, SIAM J. Comput., 18 (1989), pp. 56{67; M. L. Fredman, in WAE 1999, Springer, Berlin, 1999, pp. 244{258; J. Iacono and O. Ozkan, in ICALP 2014, Springer, Berlin, 2014, pp. 637{649]. Roughly speaking, we map an arbitrary heap algorithm within a natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e., the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e., the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g., [S. Pettie, in FOCS 2005, IEEE, Washington, DC, 2005, pp. 174{183; S. Pettie, in SODA 2008, ACM, New York, SIAM, Philadelphia, 2008, pp. 1115{1124]). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple, and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal [J. M. Lucas, Canonical Forms for Competitive Binary Search Tree Algorithms, Tech. rep. DCS-TR-250, Rutgers University, New Brunswick, NJ, 1988; J. Munro, in Algorithms|ESA 2000, Lecture Notes in Comput. Sci. 1879, Springer, Berlin, Heidelberg, 2000, pp. 338{345; E. D. Demaine et al., in SODA 2009, AMC, New York, SIAM, Philadelphia, 2009, pp. 496{505]. Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. As corollaries of results known for Greedy, we obtain instance-specific upper bounds for the smooth heap, with applications in adaptive sorting. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g., it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a \power-of-two-choices" type of heuristic. [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]

A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is, constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is β-Hӧlder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould, and Toint [SIAM J. Optim., to appear] on the evaluation complexity to the inexact case: if a qth-order minimizer is sought using approximations to the first p derivatives, it is proved that a suitable approximate minimizer within ⲉ is computed by the proposed algorithm in at most O (ⲉ−p+β/p−q+β) iterations and at most O(|log(ⲉ)|ⲉ−p+β/p−q+β) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|log(ⲉ)|+ⲉ−p+β/p−q+β) evaluations. While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and bound-constrained first-and second-order cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive sample-size rules for subsampling methods typical of machine learning. [ABSTRACT FROM AUTHOR]

New block modified Gram--Schmidt (BMGS) methods for the Q-R factorization of a full column rank matrix X × Rm×n, m× n, are considered. Such methods factor X into Q × Rm×n and an upper triangular R × Rm×n such that X = QR, where, in exact arithmetic, Q is left orthogonal (i.e., QT Q = In). Gram--Schmidt-based algorithms play an important role in the implementation of Krylov space methods, such as GMRES, Arnoldi, and Lanczos. For these applications, the left orthogonal factor Q is needed and the matrix is produced either one column at a time or one block of columns at a time. For block implementations of Krylov methods, a block of columns of X is introduced at each step, and a new block of columns of Q must then be produced. That is a task for which BMGS methods are ideally suited. However, for these Krylov methods to converge properly, the BMGS algorithms need to have numerical behavior that is similar to that of modified Gram--Schmidt. To design such BMGS algorithms, we build upon the block Householder representation of Schreiber and Van Loan [SIAM J. Sci. Stat. Comput., 10 (1989), pp. 53--57] and an observation by Charles Sheffield analyzed by Paige [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 565--583] about the relationship between modified Gram--Schmidt and Householder Q-R factorization. Our new BMGS algorithms exploit the Sheffield framework so that they share a similar relationship to Householder Q-R and thus have error analysis properties similar to modified Gram--Schmidt. The last BMGS algorithm developed is based entirely upon matrix multiplications and the "tall, skinny" Q-R (TSQR) factorization--two operations that have been studied extensively for cache-based architectures and distributed architectures. It is shown that if the TSQR part of the BMGS algorithm satisfies error analysis properties connected to the Sheffield structure, then so does the entire BMGS algorithm. Thus new criteria for when a BMGS algorithm has error analysis properties similar to those of MGS are proposed. [ABSTRACT FROM AUTHOR]

We extend the proof in [M. Crouzeix and C. Palencia, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 649-655] to show that other regions in the complex plane are K-spectral sets. In particular, we show that various annular regions are (1 + √2)-spectral sets and that a more general convex region with a circular hole or cutout is a (3 + 2 √3)-spectral set. We demonstrate how these results can be used to give bounds on the convergence rate of the GMRES algorithm for solving linear systems and on that of rational Krylov subspace methods for approximating f(A)b, where A is a square matrix, b is a given vector, and f is a function that can be uniformly approximated on such a region by rational functions with poles outside the region. [ABSTRACT FROM AUTHOR]

In the Steiner point removal problem, we are given a weighted graph G = (V,E) and a set of terminals K ⊏ V of size k. The objective is to find a minor M of G with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer, and Nguyen [SIAM J. Comput., 44 (2015), pp. 975--995] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most O(log5 κ). Cheung [Proceedings of the 29th Annual ACM/SIAM Symposium on Discrete Algorithms, 2018, pp. 1353--1360] improved the analysis of the same algorithm, bounding the distortion by O(log² κ). We devise a novel and simpler algorithm (called the Relaxed-Voronoi algorithm) which incurs distortion O(log κ). This algorithm can be implemented in almost linear time (O(| E| log | V |)). [ABSTRACT FROM AUTHOR]

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput., 23 (1994), pp. 864-894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14-23]. We present approximation algorithms for 0-EXTENSION. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71-101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput., 25 (1996), pp. 235-251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least c&radiclg k; for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations. [ABSTRACT FROM AUTHOR]