6566254
On k-Median clustering in high dimensions
We study approximation algorithms for <i>k</i>-median clustering. We obtain small coresets for <i>k</i>-median clustering in metric spaces as well as in Euclidean spaces. Specifically, in R<sup>d</sup>, those coresets are of size with only <i>polynomial</i> dependency on <i>d</i>. This leads to a (1 + ε)-approximation algorithm for <i>k</i>-median clustering in R<sup>d</sup>, with running time <i>O</i>(<i>ndk</i> +2<sup>(k/ε)<sup><i>o</i>(1)</sup></sup><i>d</i><sup>2</sup><i>n</i>σ), for any σ > 0. This is an improvement over previous results [5, 20, 21]. We also provide fast constant factor approximation algorithms for <i>k</i>-median clustering in finite metric spaces.We use those coresets to compute (1 + ε)-approximation <i>k</i>-median clustering in the streaming model of computation, using only <i>O</i>(<i>k</i><sup>2</sup><i>de</i><sup>-2</sup>log<sup>8</sup> <i>n</i>) space, where the points are taken from R<sup>d</sup>. This is the first streaming algorithm, for this problem, that has space complexity with only <i>polynomial</i> dependency on the dimension.
16132278
A constant factor approximation algorithm for k-median clustering with outliers
We consider the k-median clustering with outliers problem: Given a finite point set in a metric space and parameters k and m, we want to remove m points (called outliers), such that the cost of the optimal k-median clustering of the remaining points is minimized. We present the first polynomial time constant factor approximation algorithm for this problem.
618005
Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O(log n) colors, with high probability.
 We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log3n) colors. This is the first efficient (i.e, using polylog(n) colors) deterministic online CF coloring algorithm for this problem.
11635081
Cost-Aware Caching Algorithms for Distributed Storage Servers
We study replacement algorithms for non-uniform access caches that are used in distributed storage systems. Considering access latencies as major costs of data management in such a system, we show that the total cost of any replacement algorithm is bounded by the total costs of evicted blocks plus the total cost of the optimal off-line algorithm (OPT). We propose two off-line heuristics: MIN-d and MIN-cod, as well as an on-line algorithm: HD-cod, which can be run efficiently and perform well at the same time. 
 
Our simulation results with Storage Performance Council (SPC)'s storage server traces show that: (1) for off-line workloads, MIN-cod performs as well as OPT in some cases, all is atmost three times worse in all test case; (2) for on-line workloads, HD-cod performs closely to the best algorithms in all cases, and is the single algorithm that performs well in all test cases, including the optimal on-line algorithm (Landlord). Our study suggests that the essential issue to be considered be the trade-off between the costs of victim blocks and the total number of evictions in order to effectively optimize both efficiency and performance of distributed storage cache replacement algorithms.
16063876
How to play a coloring game against a color-blind adversary
We study the problem of conflict-free (CF) coloring of a set of points in the plane, in an online fashion, with respect to halfplanes, nearly-equal axis-parallel rectangles, and congruent disks. As a warm-up exercise, the online CF coloring of points on the line with respect to intervals is also considered. We present randomized algorithms in the oblivious adversary model, where the adversary does not see the colors used. For the problems considered, the algorithms always produce valid CF colorings, and use O(logn) colors with high probability (these bounds are optimal in the worst case). Our randomized online algorithms are considerably simpler than previous algorithms for this problem and use fewer colors.We also present a deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(polylog(n)) colors. This is the first efficient deterministic online CF coloring algorithm for this problem.
16722943
The Euclidean Orienteering Problem Revisited
We consider the rooted orienteering problem: Given a set $P$ of $n$ points in the plane, a starting point $r \in P$, and a length constraint $B$, one needs to find a path starting from $r$ that visits as many points of $P$ as possible and of length not exceeding $B$. We present a $(1-\varepsilon)$-approximation algorithm for this problem that runs in $n^{O(1/\varepsilon)}$ time; the computed path visits at least $ (1-\varepsilon)k_{\mathrm{opt}}$ points of $P$, where $k_{\mathrm{opt}}$ is the number of points visited by an optimal solution. This is the first polynomial time approximation scheme for this problem. The algorithm also works in higher dimensions.
6117831
MATLAB Simulink modeling and simulation of LVI-based primal-dual neural network for solving linear and quadratic programs
In view of parallel-processing nature and circuit-implementation convenience, recurrent neural networks are often employed to solve optimization problems. Recently, a primal-dual neural network based on linear variational inequalities (LVI) was developed by Zhang et al. for the online solution of linear-programming (LP) and quadratic-programming (QP) problems simultaneously subject to equality, inequality and bound constraints. For the final purpose of field programmable gate array (FPGA) and application-specific integrated circuit (ASIC) realization, we investigate in this paper the MATLAB Simulink modeling and simulative verification of such an LVI-based primal-dual neural network (LVI-PDNN). By using click-and-drag mouse operations in MATLAB Simulink environment, we could quickly model and simulate complicated dynamic systems. Modeling and simulative results substantiate the theoretical analysis and efficacy of the LVI-PDNN for solving online the linear and quadratic programs.
6083596
Improved learning algorithms for mixture of experts in multiclass classification
Mixture of experts (ME) is a modular neural network architecture for supervised learning. A double-loop Expectation-Maximization (EM) algorithm has been introduced to the ME architecture for adjusting the parameters and the iteratively reweighted least squares (IRLS) algorithm is used to perform maximization in the inner loop [Jordan, M.I., Jacobs, R.A. (1994). Hierarchical mixture of experts and the EM algorithm, Neural Computation, 6(2), 181-214]. However, it is reported in literature that the IRLS algorithm is of instability and the ME architecture trained by the EM algorithm, where IRLS algorithm is used in the inner loop, often produces the poor performance in multiclass classification. In this paper, the reason of this instability is explored. We find out that due to an implicitly imposed incorrect assumption on parameter independence in multiclass classification, an incomplete Hessian matrix is used in that IRLS algorithm. Based on this finding, we apply the Newton-Raphson method to the inner loop of the EM algorithm in the case of multiclass classification, where the exact Hessian matrix is adopted. To tackle the expensive computation of the Hessian matrix and its inverse, we propose an approximation to the Newton-Raphson algorithm based on a so-called generalized Bernoulli density. The Newton-Raphson algorithm and its approximation have been applied to synthetic data, benchmark, and real-world multiclass classification tasks. For comparison, the IRLS algorithm and a quasi-Newton algorithm called BFGS have also been applied to the same tasks. Simulation results have shown that the use of the proposed learning algorithms avoids the instability problem and makes the ME architecture produce good performance in multiclass classification. In particular, our approximation algorithm leads to fast learning. In addition, the limitation of our approximation algorithm is also empirically investigated in this paper.
17434449
On Two Multigrid Algorithms for Modeling Variational Multiphase Image Segmentation
In this paper, we present two related multigrid algorithms for multiphase image segmentation. Algorithm I solves the model by Vese-Chan. We first generalize our recently developed multigrid method to this multiphase segmentation model (MG1); we also give a local Fourier analysis for the local smoother which leads to a new and more effective smoother. Although MG1 is found many magnitudes faster than the fast method of additive operator splitting (AOS), both algorithms are not robust with regard to the initial guess. To overcome this dependence on the initial guess, we consider a hierarchical segmentation model which achieves multiphase segmentation by repeated use of the Chan-Vese two-phase model; our algorithm II solves this model by a multigrid algorithm (MG2). Numerical experiments show that both algorithms are efficient and in particular MG2 is more robust than MG1 with respect to initial guesses. AMS subject classifications: 68U10, 65F10, 65K10.
41045084
Parallel algorithms of the Purcell method for direct solution of linear systems
In this paper, we first demonstrate that the classical Purcell's vector method when combined with row pivoting yields a consistently small growth factor in comparison to the well-known Gauss elimination method, the Gauss-Jordan method and the Gauss-Huard method with partial pivoting. We then present six parallel algorithms of the Purcell method that may be used for direct solution of linear systems. The algorithms differ in ways of pivoting and load balancing. We recommend algorithms V and VI for their reliability and algorithms III and IV for good load balance if local pivoting is acceptable. Some numerical results are presented.
13931461
Accurate sequence-based prediction of catalytic residues
MOTIVATION
Prediction of catalytic residues provides useful information for the research on function of enzymes. Most of the existing prediction methods are based on structural information, which limits their use. We propose a sequence-based catalytic residue predictor that provides predictions with quality comparable to modern structure-based methods and that exceeds quality of state-of-the-art sequence-based methods.


RESULTS
Our method (CRpred) uses sequence-based features and the sequence-derived PSI-BLAST profile. We used feature selection to reduce the dimensionality of the input (and explain the input) to support vector machine (SVM) classifier that provides predictions. Tests on eight datasets and side-by-side comparison with six modern structure- and sequence-based predictors show that CRpred provides predictions with quality comparable to current structure-based methods and better than sequence-based methods. The proposed method obtains 15-19% precision and 48-58% TP (true positive) rate, depending on the dataset used. CRpred also provides confidence values that allow selecting a subset of predictions with higher precision. The improved quality is due to newly designed features and careful parameterization of the SVM. The features incorporate amino acids characterized by the highest and the lowest propensities to constitute catalytic residues, Gly that provides flexibility for catalytic sites and sequence motifs characteristic to certain catalytic reactions. Our features indicate that catalytic residues are on average more conserved when compared with the general population of residues and that highly conserved amino acids characterized by high catalytic propensity are likely to form catalytic sites. We also show that local (with respect to the sequence) hydrophobicity contributes towards the prediction.