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

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]

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]

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]

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]

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]

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]

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]

Aiming at the problems of complex background, variety of change types, missing detection and rough boundary recognition in high-resolution remote sensing image of the same region, this paper proposed a high-resolution remote sensing image building change detection algorithm based on Siam-UNet++network. The algorithm used UNet++as the backbone extraction network. In the encoder phase, it applied the Siam-diff structure to extract the change features of the two sequential images, and employed the attention mechanism after the up sampling and lateral jump path connection in the decoding stage to highlight the building change features and inhibit the network learning from other types of features. Meanwhile, it used the MSOF strategy to weight and fuse feature information of different semantic levels, which improved the accuracy of building change detection. Finally, it adopted a sliding window method to predict large-scale remote sensing images, reducing the hole pattern generated by the change result map during the splicing process. The experimental results demonstrate that proposed algorithm shows better performance than other models. [ABSTRACT FROM AUTHOR]

This paper concentrates on studying the application of fuzzy soft sets and the construction of an algorithm to identify a better approach flood alarm prediction model that applies to eight selected provinces sites in Northern Thailand. Finally, an example is provided to show which of the methods can be successfully used to predict potential flood in the future. [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]

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that Ω (n) space is necessary to yield a 2 / 2 + ε approximation of the optimum value; they also presented an algorithm that yields a 2 / 2 − ε approximation of the optimum value using O (ε − 2 log ⁡ n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o (m n) space. We present randomized single-pass algorithms that w.h.p.1 yield: • A 1 − ε approximation using O ˜ (n / ε 3) space and exponential post-processing time • A 3 / 4 − ε approximation using O ˜ (n / ε) space and polynomial post-processing time. Our ideas also extend to dynamic streams. However, we show that the streaming k -SAT problem, which asks whether one can satisfy all size- k input clauses, must use Ω (n k) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a O ˜ (n 2 / ε 2) space algorithm, which is sublinear when m = ω (n) , that yields an α + ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2 f n approximation using O ˜ (n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use Ω (m n) space. [ABSTRACT FROM AUTHOR]