Search

We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207‐211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109‐138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence and complexity properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and more stable than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109‐138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one. [ABSTRACT FROM AUTHOR]

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]

This paper mainly studies the gradient-based Jacobi-type algorithms to maximize two classes of homogeneous polynomials with orthogonality constraints, and establish their convergence properties. For the first class of homogeneous polynomials subject to a constraint on a Stiefel manifold, we reformulate it as an optimization problem on a unitary group, which makes it possible to apply the gradient-based Jacobi-type (Jacobi-G) algorithm. Then, if the subproblem can always be represented as a quadratic form, we establish the global convergence of Jacobi-G under any one of three conditions. The convergence result for the first condition is an easy extension of the result by Usevich, Li, and Comon [SIAM J. Optim. 30 (2020), pp. 2998–3028], while other two conditions are new ones. This algorithm and the convergence properties apply to the well-known joint approximate symmetric tensor diagonalization. For the second class of homogeneous polynomials subject to constraints on the product of Stiefel manifolds, we reformulate it as an optimization problem on the product of unitary groups, and then develop a new gradient-based multiblock Jacobi-type (Jacobi-MG) algorithm to solve it. We establish the global convergence of Jacobi-MG under any one of the above three conditions, if the subproblem can always be represented as a quadratic form. This algorithm and the convergence properties are suitable to the well-known joint approximate tensor diagonalization. As the proximal variants of Jacobi-G and Jacobi-MG, we also propose the Jacobi-GP and Jacobi-MGP algorithms, and establish their global convergence without any further condition. Some numerical results are provided indicating the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In a very interesting paper (SIAM J. Control Optim. 37(3): 765–776, 1999), Solodov and Svaiter introduced an effective projection algorithm with linesearch for finding a solution of a variational inequality problem (VIP) in Euclidean space. They showed that the iterative sequence generated by their algorithm converges to a solution of (VIP) under the main assumption that the cost mapping is pseudomonotone and continuous. In this paper, we propose to modify this algorithm for solving variational inequality problems in which the cost mapping is not required to be satisfied any pseudomonotonicity. Moreover, we do not use the embedded projection methods as in methods used in literature and the linesearch procedure is not necessary when the cost mapping is Lipschitz. Several numerical examples are also provided to illustrate the efficient of the proposed algorithms. [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]

This paper presents the Hybrid and Self-Adaptive Differential Evolution algorithms (HSADE) to solve an egg distribution problem in Thailand. We introduce and formalize a model for a multi-product, multi-depot vehicle routing problem with a time window, a heterogeneous fleet and inventory restrictions. The goal of the problem is to minimize the total cost. The multiple products comprise customers' demands with different egg sizes. This paper presents a Mixed Integer Linear Programming (MILP) model, an initial solution-based constructive heuristic, a new self-adaptive mutation strategy, and a neighborhood search structure with the probability to improve DE. The two measurements of criteria are the heuristic performance (HP) compared with the solution obtained by MILP and the relative improvement (RI) of the solution compared with Thailand's current egg distribution practice. The computational results show that the performance of HSADE is better than the current practice, and HSADE can provide on average a 14.13% improvement in total cost. Additionally, our proposed algorithm can be applied to similar agriculture logistics in Thailand and worldwide. [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]

Educational data classification has become an effective tool for exploring the hidden pattern or relationship in educational data and predicting students' performance or teachers' competency. This study proposes a new method based on machine learning algorithms to predict the technology-integrated competency of pre-service mathematics teachers. In this paper, we modified the inertial subgradient extragradient algorithm for pseudomonotone equilibrium and proved the weak convergence theorem under some suitable conditions in Hilbert spaces. We then applied to solve data classification by extreme learning machine using the dataset comprised of the technology-integrated competency of 954 pre-service mathematics teachers in a university in northern Thailand, longitudinally collected for five years. The flexibility of our algorithm was shown by comparisons of the choice of different parameters. The performance was calculated and compared with the existing algorithms to be implemented for prediction. The results show that the proposed method achieved a classification accuracy of 81.06%. The predictions were implemented using ten attributes, including demographic information, skills, and knowledge relating to technology developed throughout the teacher education program. Such data driven studies are significant for establishing a prospective teacher competency analysis framework in teacher education and contributing to decision-making for policy design. [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]

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]

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]

This study aims to select the ideal mixture of small and medium-sized destinations and attractions in Thailand's Ubon Ratchathani Province in order to find potential wellness destinations and attractions. In the study region, 46 attractions and destinations were developed as the service sectors for wellness tourism using the designed wellness framework and the quality level of the attractions and destinations available on social media. Distinct types of tourists, each with a different age and gender, comprise a single wellness tourist group. Due to them, even with identical attractions and sites, every traveler has a different preference. A difficult task for travel agencies is putting together combinations of attractions and places for each tourist group. In this paper, the mathematical formulation of the suggested problem is described, and the optimal solution is achieved using Lingo v.16. Unfortunately, the large size of test instances cannot be solved with Lingo v16. However, the large-scale problem, particularly the case study in the target area, has been solved using a metaheuristic method called AMIS. According to the computation in the final experiment, AMIS can raise the solution quality across all test instances by an average of 3.83 to 8.17 percent. Therefore, it can be concluded that AMIS outperformed all other strategies in discovering the ideal solution. AMIS, GA and DE may lead visitors to attractions that generate 29.76%, 29.58% and 32.20%, respectively, more revenue than they do now while keeping the same degree of preference when the number of visitors doubles. The attractions' and destinations' utilization has increased by 175.2 percent over the current situation. This suggests that small and medium-sized enterprises have a significantly higher chance of flourishing in the market. [ABSTRACT FROM AUTHOR]

Ruelle (1997 Commun. Math. Phys. 187 227â€"41; 2003 Commun. Math. Phys. 234 185â€"90) (see also Jiang 2012 Ergod. Theor. Dynam. Syst. 32 1350â€"69) gave a formula for linear response of transitive Anosov diffeomorphisms. Recently, practically computable realizations of Ruelle’s formula have emerged that potentially enable sensitivity analysis of certain high-dimensional chaotic numerical simulations encountered in the applied sciences. In this paper, we provide full mathematical justification for the convergence of one such efficient computation, the spaceâ€"split sensitivity, or S3, algorithm (Chandramoorthy and Wang 2022 SIAM J. Appl. Dyn. Syst. 21 735â€"81). In S3, Ruelle’s formula is computed as a sum of two terms obtained by decomposing the perturbation vector field into a coboundary and a remainder that is parallel to the unstable direction. Such a decomposition results in a splitting of Ruelle’s formula that is amenable to efficient computation. We prove the existence of the S3 decomposition and the convergence of the computations of both resulting components of Ruelle’s formula. [ABSTRACT FROM AUTHOR]

This paper applies an algorithm for the convolution of compactly supported Legendre series (the CONLeg method) (cf. Hale and Townsend, An algorithm for the convolution of Legendre series. SIAM J. Sci. Comput., 2014, 36, A1207–A1220), to pricing European-type, early-exercise and discrete-monitored barrier options under a Lévy process. The paper employs Chebfun (cf. Trefethen et al., Chebfun Guide, 2014 (Pafnuty Publications: Oxford), Available online at: ) in computational finance and provides a quadrature-free approach by applying the Chebyshev series in financial modelling. A significant advantage of using the CONLeg method is to formulate option pricing and option Greek curves rather than individual prices/values. Moreover, the CONLeg method can yield high accuracy in option pricing when the risk-free smooth probability density function (PDF) is smooth/non-smooth. Finally, we show that our method can accurately price options deep in/out of the money and with very long/short maturities. Compared with existing techniques, the CONLeg method performs either favourably or comparably in numerical experiments. [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]

Motivated by the convergence result of mirror-descent algorithms to market equilibria in linear Fisher markets, it is natural for one to consider designing dynamics (specifically, iterative algorithms) for agents to arrive at linear Arrow-Debreu market equilibria. Jain (SIAM J. Comput. 37(1), 303–318, 2007) reduced equilibrium computation in linear Arrow-Debreu markets to the equilibrium computation in bijective markets, where everyone is a seller of only one good and a buyer for a bundle of goods. In this paper, we design an algorithm for computing linear bijective market equilibrium, based on solving the rational convex program formulated by Devanur et al. The algorithm repeatedly alternates between a step of gradient-descent-like updates and a distributed step of optimization exploiting the property of such convex program. Convergence can be ensured by a new analysis different from the analysis for linear Fisher market equilibria. [ABSTRACT FROM AUTHOR]

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f (pw) n o (pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl + Δ , where tl is the tree-length and Δ the maximum-degree of the input graph. [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]

In this paper, we combine the S-iteration process introduced by Agarwal et al. (J. Nonlinear Convex Anal., 8(1), 61–79 2007) with the proximal point algorithm introduced by Rockafellar (SIAM J. Control Optim., 14, 877–898 1976) to propose a new modified proximal point algorithm based on the S-type iteration process for approximating a common element of the set of solutions of convex minimization problems and the set of fixed points of nearly asymptotically quasi-nonexpansive mappings in the framework of CAT(0) spaces and prove the △-convergence of the proposed algorithm for solving common minimization problem and common fixed point problem. Our result generalizes, extends and unifies the corresponding results of Dhompongsa and Panyanak (Comput. Math. Appl., 56, 2572–2579 2008), Khan and Abbas (Comput. Math. Appl., 61, 109–116 2011), Abbas et al. (Math. Comput. Modelling, 55, 1418–1427 2012) and many more. [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]

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]

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]

An ideal image is desirable to faithfully represent the real-world scene. However, the observed images from imaging system are typically involved in the illumination of light. As the human visual system (HVS) is capable of perceiving identical color with spatially varying illumination, retinex theory is established to probe the rationale of HVS on perceiving color. In the realm of image processing, the retinex models are devoted to diminishing illumination effects from observed images. In this paper, following the recent work by Ng and Wang (SIAM J. Imaging Sci. 4:345-356, 2011), we develop a parallel operator splitting algorithm tailored for the constrained total-variation retinex model, in which all the resulting subproblems admit closed form solutions or can be tractably solved by some subroutines without any internally nested iterations. The global convergence of the novel algorithm is analysed on the perspective of variational inequality in optimization community. Preliminary numerical simulations demonstrate the promising performance of the proposed algorithm. [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]

For a positive integer k, a radio k-coloring of a simple connected graph G = (V(G), E(G)) is a mapping f : V (G) → { 0 , 1 , 2 , ... } such that | f (u) - f (v) | ≥ k + 1 - d (u , v) for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is the maximum integer assigned by it to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number of G. In this paper, we propose an improved upper bound of radio k-chromatic number for a given graph against the other which is due to Saha and Panigrahi (in: Arumugan, Smyth (eds) Combinatorial algorithms (IWOCA 2012). Lecure notes in computer science, vol 7643, Springer, Berlin, 2012). The computational study shows that the proposed algorithm overcomes the previous algorithm. We introduce a polynomial algorithm [differs from the other that is due to Liu and Zhu (SIAM J Discrete Math 19(3):610–621, 2005)] which determines the radio number of the path graph Pn. Finally, we propose a new integer linear programming model for the radio k-coloring problem. The computational study between the proposed algorithm and LINGO solver shows that the proposed algorithm overcomes LINGO solver. [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]

This paper aims to propose an algorithm to construct a delivery-sequencing/inventory-allocation plan used to control a supply chain in the operational planning level. The algorithm which is mainly based on the improving search technique begins by determining a suitable initial sequence of customer orders, allocating available inventory and determining inventory replenishment plan according to the sequence, calculating the interesting goals, and finally searching the appropriate sequence of customer orders using a proposed pairwise interchange technique. The sequence of the customer order is considered appropriate if it can simultaneously give most preferable two goals: minimizing the total penalties paid by the supply chain, and minimizing the average cost of fulfilling each product unit transferred to customers. The efficiency of the proposed algorithm is tested by the numerical experiments based on real data from a selected supply chain in Thailand, namely the food-ingredient industry. Statistical results show that the proposed algorithm significantly outperforms the current planning heuristics used in the industry and some other well-known heuristics. [ABSTRACT FROM AUTHOR]

Driving in the wrong direction is one of the main reasons that cause road accidents in Thailand. To efficiently detect wrong direction driving vehicles, we proposed a system that can track those moving vehicles from CCTVs using deep learning and image processing techniques. Our proposed system is composed of two main algorithms: Road Lane Boundary detection from CCTV algorithm (RLB-CCTV) and Majority-Based Correct Direction Detection algorithm (MBCDD). In this paper, we introduced the RLB-CCTV algorithm and the enhanced version of MBCDD algorithms for detecting road boundaries and wrong-direction driving vehicles. Based on our experiments, our system can identify the road lane boundary and track vehicles driving in the wrong direction on each lane with an accuracy of 96.61%. [ABSTRACT FROM AUTHOR]

Distributed algorithms are receiving renewed attention across multiple disciplines due to the dramatically increasing demand of big data processing. We consider a class of consensus optimization problems over a static network system of multiple agents, where each of local cost functions is a sum of a smooth function and a non-Lipschitz regularization term. This kind of problems is widely found in scientific and engineering areas such as machine learning and data analysis. Inspired by Bian and Chen (SIAM J. Opt. 23(3), 1718–1741 2017), we propose a decentralized smoothing quadratic regularization algorithm (abbreviated as D-SQRA) for solving the composite consensus problem with non-Lipschitz singularities. To some extent, D-SQRA can be seen as an extension in the decentralized setup of the smoothing quadratic regularization algorithm (SQRA) proposed in (SIAM J. Opt. 23(3), 1718–1741 2017). Our main contribution is to show that D-SQRA can inherit the theoretical properties of its centralized counterpart, i.e., SQRA, in both sides of convergence and worst-case iteration complexity to achieve an ϵ scaled stationary point. We also present some numerical examples on sparse sensing problems based on synthetic and real datasets to corroborate the effectiveness of the proposed decentralized algorithm. [ABSTRACT FROM AUTHOR]

In Zhang et al. (accepted by SIAM J. Optim., ), we developed a class of derivative-free algorithms, called DFLS, for least-squares minimization. Global convergence of the algorithm as well as its excellent numerical performance within a limited computational budget was established and discussed in the same paper. Here we would like to establish the local quadratic convergence of the algorithm for zero residual problems. Asymptotic convergence performance of the algorithm for both zero and nonzero problems is tested. Our numerical experiments indicate that the algorithm is also very promising for achieving high accuracy solutions compared with software packages that do not exploit the special structure of the least-squares problem or that use finite differences to approximate the gradients. [ABSTRACT FROM AUTHOR]

Copyright of Application Research of Computers / Jisuanji Yingyong Yanjiu is the property of Application Research of Computers Edition and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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]

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 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]

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]

The central issue of this paper is that one can develop emergent macro-dynamics from micro agent models and that the resulting models fall very much in the complexity-chaos line of the development of theory. The core theoretical contribution is a presentation of a clear, sensical, and potentially very powerful architecture for developing algorithms for the embedding of levels—the so-called master equation approach—and its comparison with alternative architectures. Finally, to illustrate the strategy and to demonstrate that the approach produces interesting and useful results, we give an application: a multilevel simulation model of military coups d'état, which is tested using data from Thailand between 1932 and 1992. [ABSTRACT FROM AUTHOR]

We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim. , 28 , 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving |$\epsilon $| -approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim. , 28 , 1448–1477). [ABSTRACT FROM AUTHOR]

We consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method Lucidi (J. Optim. Theory Appl. 67(2): 227–245, 1990) developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure Paquette and Scheinberg (SIAM J. Optim. 30(1): 349–376 2020) into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive 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]

As a component of robust designation field, the IPA technique is reputed for providing a quantified index of expectation value from multiple patients' biological index series. The expectation value can be a specific drug in blood concentration reading, or the potential risk of a patient with a clinical syndrome, or the optimal trigger timing for CTA. This study verified the inverse problem algorithm (IPA) by integrated case studies in preventive medicine. The risk factors can be Age, BSA (body surface area), Sugar AC, MAP (mean artery pressure), or others. The risk factor index is normalized to eliminate the physical dimensionality and yield a quantified index between -1.0 and +1.0, whereas the middle point, 0.0, implies the average risk factor index. The quantified indices of patients are organized into a vast data matrix for deriving the inverse matrix and obtaining the column matrix of the compromised solution. This study preset the STATISTICA program to derive the solution according to default quasi-Newton or Rosenbrock analysis. The derived solution can be defined as a nonlinear semi-empirical formula with multiple terms to express the specific expectation value. Accordingly, six IPA-related papers are comprehensively integrated to explore the applicability and critical points in adopting the IPA technique for preventive medicine tasks. Besides, the interpretation of cross-interactions among risk factors to affect the performing of IPA computation and the convergence rate of a semi-empirical formula related to the final constant term are also analyzed and discussed in detail. The integrated IPA technique is instrumental in exploring potential syndromes in preventive medicine. [ABSTRACT FROM AUTHOR]

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP for a restricted class of instances, called α -small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O (log (1 / (1 - α))) -approximation algorithm. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [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]

For solving strongly convex optimization problems, we propose and study the global convergence of variants of the accelerated hybrid proximal extragradient (A-HPE) and large-step A-HPE algorithms of R.D.C. Monteiro and B.F. Svaiter [An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM J. Optim. 23 (2013), pp. 1092–1125.]. We prove linear and the superlinear O (k − k (p − 1 p + 1) ) global rates for the proposed variants of the A-HPE and large-step A-HPE methods, respectively. The parameter p ≥ 2 appears in the (high-order) large-step condition of the new large-step A-HPE algorithm. We apply our results to high-order tensor methods, obtaining a new inexact (relative-error) tensor method for (smooth) strongly convex optimization with iteration-complexity O (k − k (p − 1 p + 1) ) . In particular, for p = 2, we obtain an inexact proximal-Newton algorithm with fast global O (k − k / 3) convergence rate. [ABSTRACT FROM AUTHOR]