A mean field model for a class of garbage collection algorithms in flash-based solid state drives

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $\mathcal {C}$ of GC algorithms. Apart from the Random GC algorithm, class $\mathcal {C}$ includes two novel GC algorithms: the $d$ -Choices GC algorithm, that selects $d$ blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50{,}000$ blocks). We further show that the $d$ -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $d$ values, e.g., $d = 10$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for $b \ge 64$ ).     

An iterated-tabu-search heuristic for a variant of the partial set covering problem

In this paper, we propose a heuristic algorithm to solve a new variant of the partial set covering problem. In this variant, each element $e_i$ has a gain $g_i$ (i.e., a positive profit), each set $s_j$ has a cost $c_j$ (i.e., a negative profit), and each set $s_j$ is part of a unique group $G_k$ that has a fixed cost $f_k$ (i.e., a negative profit). The objective is to maximize profit and it is not necessary to cover all of the elements. We present an industrial application of the model and propose a hybrid heuristic algorithm to solve it; the proposed algorithm is an iterated-local-search algorithm that uses two levels of perturbations and a tabu-search heuristic. Whereas the first level of perturbation diversifies the search around the current local optimum, the second level of perturbation performs long jumps in the search space to help escape from local optima with large basins of attraction. The proposed algorithm is evaluated on thirty real-world problems and compared to a memetic algorithm. Computational results show that most of the solutions found by ITS are either optimal or very close to optimality.     

Counting and Sampling Minimum Cuts in Genus g Graphs

Let \(G\) be a directed graph with \(n\) vertices embedded on an orientable surface of genus \(g\) with two designated vertices \(s\) and \(t\) . We show that computing the number of minimum \((s,t)\) -cuts in \(G\) is fixed-parameter tractable in \(g\) . Specifically, we give a \(2^{O(g)} n^2\) time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are no prior results that are fixed-parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an \((s,t)\) -minimum cut uniformly at random in \(O(n \log n)\) time per sample.     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

Optimal Reconstruction Might be Hard

Given as input a point set $\mathcal S $ that samples a shape $\mathcal A $ , the condition required for inferring Betti numbers of $\mathcal A $ from $\mathcal S $ in polynomial time is much weaker than the conditions required by any known polynomial time algorithm for producing a topologically correct approximation of $\mathcal A $ from $\mathcal S $ . Under the former condition which we call the weak precondition, we investigate the question whether a polynomial time algorithm for reconstruction exists. As a first step, we provide an algorithm which outputs an approximation of the shape with the correct Betti numbers under a slightly stronger condition than the weak precondition. Unfortunately, even though our algorithm terminates, its time complexity is unbounded. We then identify at the heart of our algorithm a test which requires answering the following question: given 2 two-dimensional simplicial complexes $L \subset K$ , does there exist a simplicial complex containing $L$ and contained in $K$ which realizes the persistent homology of $L$ into $K$ ? We call this problem the homological simplification of the pair $(K,L)$ and prove that this problem is NP-complete, using a reduction from 3SAT.     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

Linear complementarity as absolute value equation solution

We consider the linear complementarity problem (LCP): $Mz+q\ge 0, z\ge 0, z^{\prime }(Mz+q)=0$ as an absolute value equation (AVE): $(M+I)z+q=|(M-I)z+q|$ , where $M$ is an $n\times n$ square matrix and $I$ is the identity matrix. We propose a concave minimization algorithm for solving (AVE) that consists of solving a few linear programs, typically two. The algorithm was tested on 500 consecutively generated random solvable instances of the LCP with $n=10, 50, 100, 500$ and 1,000. The algorithm solved $100\,\%$ of the test problems to an accuracy of $10^{-8}$ by solving 2 or less linear programs per LCP problem.     

Affine Types of L -Polyhedra for 5 -lattices

We construct an algorithm for deducing all affinely nonequivalent types of $L$ -polyhedra on n-lattices, where $n \leqslant 5$ . The computational part of the algorithm designed for calculations on a personal computer is based on the relationship between the geometry of lattices and the theory of hypermetric spaces. For the first time, a complete list of affine types ( $139$ types) of $L$ -polyhedra on $5 $ -lattices is obtained.     

Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

In this paper, we study the problem of moving $n$ n sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an $O(n^2\log n)$ O ( n 2 log n ) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes $O(n^2)$ O ( n 2 ) time. We present an $O(n\log n)$ O ( n log n ) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes $O(n)$ O ( n ) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in $O(n)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution.     

Algorithmic aspects of Steiner convexity and enumeration of Steiner trees

For a set \(W\) of vertices of a connected graph \(G=(V(G),E(G))\) , a Steiner W-tree is a connected subgraph \(T\) of \(G\) such that \(W\subseteq V(T)\) and \(|E(T)|\) is minimum. Vertices in \(W\) are called terminals. In this work, we design an algorithm for the enumeration of all Steiner \(W\) -trees for a constant number of terminals, which is the usual scenario in many applications. We discuss algorithmic issues involving space requirements to compactly represent the optimal solutions and the time delay to generate them. After generating the first Steiner \(W\) -tree in polynomial time, our algorithm enumerates the remaining trees with \(O(n)\) delay (where \(n=|V(G)|\) ). An algorithm to enumerate all Steiner trees was already known (Khachiyan et al., SIAM J Discret Math 19:966–984, 2005), but this is the first one achieving polynomial delay. A by-product of our algorithm is a representation of all (possibly exponentially many) optimal solutions using polynomially bounded space. We also deal with the following problem: given \(W\) and a vertex \(x\in V(G)\setminus W\) , is \(x\) in a Steiner \(W'\) -tree for some \(\emptyset \ne W' \subseteq W\) ? This problem is investigated from the complexity point of view. We prove that it is NP-hard when \(W\) has arbitrary size. In addition, we prove that deciding whether \(x\) is in some Steiner \(W\) -tree is NP-hard as well. We discuss how these problems can be used to define a notion of Steiner convexity in graphs.     

A Probabilistic Symbolic Algorithm to Find the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set

We consider the problem of computing the minimum of a polynomial function \(g\) on a basic closed semialgebraic set \(E\subset \mathbb {R}^n\) . We present a probabilistic symbolic algorithm to find a finite set of sample points of the subset \(E^{\min }\) of \(E\) where the minimum of \(g\) is attained, provided that \(E^{\min }\) is non-empty and has at least one compact connected component.     

Clustering and classification via cluster-weighted factor analyzers

In model-based clustering and classification, the cluster-weighted model is a convenient approach when the random vector of interest is constituted by a response variable $Y$ and by a vector ${\varvec{X}}$ of $p$ covariates. However, its applicability may be limited when $p$ is high. To overcome this problem, this paper assumes a latent factor structure for ${\varvec{X}}$ in each mixture component, under Gaussian assumptions. This leads to the cluster-weighted factor analyzers (CWFA) model. By imposing constraints on the variance of $Y$ and the covariance matrix of ${\varvec{X}}$ , a novel family of sixteen CWFA models is introduced for model-based clustering and classification. The alternating expectation-conditional maximization algorithm, for maximum likelihood estimation of the parameters of all models in the family, is described; to initialize the algorithm, a 5-step hierarchical procedure is proposed, which uses the nested structures of the models within the family and thus guarantees the natural ranking among the sixteen likelihoods. Artificial and real data show that these models have very good clustering and classification performance and that the algorithm is able to recover the parameters very well.     

Newton Polytopes and Witness Sets

We present two algorithms that compute the Newton polytope of a polynomial f defining a hypersurface \({\mathcal{H}}\) in \({\mathbb{C}^n}\) using numerical computation. The first algorithm assumes that we may only compute values of f—this may occur if f is given as a straight-line program, as a determinant, or as an oracle. The second algorithm assumes that \({\mathcal{H}}\) is represented numerically via a witness set. That is, it computes the Newton polytope of \({\mathcal{H}}\) using only the ability to compute numerical representatives of its intersections with lines. Such witness set representations are readily obtained when \({\mathcal{H}}\) is the image of a map or is a discriminant. We use the second algorithm to compute a face of the Newton polytope of the Lüroth invariant, as well as its restriction to that face.     

Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable  $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine.     

Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs

We consider the online scheduling of equal-length jobs with incompatible families on \(m\) identical batch machines. Each job has a release time, a deadline and a weight. Each batch machine can process up to \(b\) jobs (which come from the same family) simultaneously as a batch, where \(b\) is called the capacity of the machines. Our goal is to determine a preemption-restart schedule which maximizes the weighted number of early jobs. For this problem, Li et al. (Inf Process Lett 112:503–508, 2012) provided an online algorithm of competitive ratio \(3+2\sqrt{2}\) for both \(b=\infty \) and \(b<\infty \) . In this paper, we study two special cases of this problem. For the case that \(m=2\) , we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3 for both \(b=\infty \) and \(b<\infty \) . For the case in which \(m=3\) , \(b=\infty \) and all jobs come from a common family, we present an online algorithm with a competitive ratio of \((8+2\sqrt{15})/3\approx 5.249\) .     

Fréchet Means for Distributions of Persistence Diagrams

Given a distribution \(\rho \) on persistence diagrams and observations \(X_{1},\ldots ,X_{n} \mathop {\sim }\limits ^{iid} \rho \) we introduce an algorithm in this paper that estimates a Fréchet mean from the set of diagrams \(X_{1},\ldots ,X_{n}\) . If the underlying measure \(\rho \) is a combination of Dirac masses \(\rho = \frac{1}{m} \sum _{i=1}^{m} \delta _{Z_{i}}\) then we prove the algorithm converges to a local minimum and a law of large numbers result for a Fréchet mean computed by the algorithm given observations drawn iid from \(\rho \) . We illustrate the convergence of an empirical mean computed by the algorithm to a population mean by simulations from Gaussian random fields.     

The reflexive least squares solutions of the matrix equation A_1X_1B_1+A_2X_2B_2+\cdots +A_lX_lB_l=Cwith a submatrix constraint

In this paper, an efficient algorithm is presented for minimizing $\|A_1X_1B_1 + A_2X_2B_2+\cdots +A_lX_lB_l-C\|$ where $\|\cdot \|$ is the Frobenius norm, $X_i\in R^{n_i \times n_i}(i=1,2,\cdots ,l)$ is a reflexive matrix with a specified central principal submatrix $[x_{ij}]_{r\leq i,j\leq n_i-r}$ . The algorithm produces suitable $[X_1,X_2,\cdots ,X_l]$ such that $\|A_1X_1B_1+A_2X_2B_2+\cdots +A_lX_lB_l-C\|=\min $ within finite iteration steps in the absence of roundoff errors. We show that the algorithm is stable any case. The algorithm requires little storage capacity. Given numerical examples show that the algorithm is efficient.     

On a Regularized Family of Models for Homogeneous Incompressible Two-Phase Flows

We consider a general family of regularized models for incompressible two-phase flows based on the Allen–Cahn formulation in \(n\) -dimensional compact Riemannian manifolds for \(n=2,3\) . The system we consider consists of a regularized family of Navier–Stokes equations (including the Navier–Stokes- \(\alpha \) -like model, the Leray- \(\alpha \) model, the modified Leray- \(\alpha \) model, the simplified Bardina model, the Navier–Stokes–Voight model, and the Navier–Stokes model) for the fluid velocity \(u\) suitably coupled with a convective Allen–Cahn equation for the order (phase) parameter \(\phi \) . We give a unified analysis of the entire three-parameter family of two-phase models using only abstract mapping properties of the principal dissipation and smoothing operators and then use assumptions about the specific form of the parameterizations, leading to specific models, only when necessary to obtain the sharpest results. We establish existence, stability, and regularity results and some results for singular perturbations, which as special cases include the inviscid limit of viscous models and the \(\alpha \rightarrow 0\) limit in \(\alpha \) models. Then we show the existence of a global attractor and exponential attractor for our general model and establish precise conditions under which each trajectory \(\left( u,\phi \right) \) converges to a single equilibrium by means of a Lojasiewicz–Simon inequality. We also derive new results on the existence of global and exponential attractors for the regularized family of Navier–Stokes equations and magnetohydrodynamics models that improve and complement the results of Holst et al. (J Nonlinear Sci 20(5):523–567, 2010). Finally, our analysis is applied to certain regularized Ericksen–Leslie models for the hydrodynamics of liquid crystals in \(n\) -dimensional compact Riemannian manifolds.     

On the cohomology of moduli spaces of (weighted) stable rational curves

We give a recursive algorithm for computing the character of the cohomology of the moduli space ${\overline{M}}_{0,n}$ of stable $n$ -pointed genus zero curves as a representation of the symmetric group $\mathbb{S }_n$ on $n$ letters. Using the algorithm we can show a formula for the maximum length of this character. Our main tool is connected to the moduli spaces of weighted stable curves introduced by Hassett.