14878951
The orienteering problem in the plane revisited
We consider the <i>orienteering problem</i>: Given a set <i>P</i> of <i>n</i> points in the plane, a starting point <i>r</i> ∈ <i>P</i>, and a length constraint <i>B</i>, one needs to find a tour starting at <i>r</i> that visits as many points of <i>P</i> as possible and of length not exceeding <i>B</i>. We present a (1−ε)-approximation algorithm for this problem that runs in <i>n</i><sup><i>O</i>(1/ε)</sup> time, and visits at least (1−ε)<i>k</i><sub>opt</sub> points of <i>P</i>, where <i>k</i><sub>opt</sub> is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.
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.
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.
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.
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.
21847139
An Analysis of Sparse Approximate Inverse Preconditioners for Boundary Integral Equations
Preconditioning techniques for dense linear systems arising from singular boundary integral equations are described and analyzed. A particular class of approximate inverse based preconditioners related to the mesh neighbor methods is known to be efficient. This paper shows that it is an operator splitting preconditioner and clusters eigenvalues for the normal equation matrix thus ensuring a fast convergence of the conjugate gradient normal method. Clustering of the eigenvalues of the preconditioned matrix and fast convergence of the generalized minimal residual method are also observed. For the type of problems considered, we demonstrate a crucial connection between two essential features of eigenvalue clustering for a sparse preconditioner---approximate inversion for a small cluster radius and operator splitting for a small cluster size. Experimental results from several boundary integral equations are presented.
17327326
UBM-based incremental speaker adaptation
This paper addresses a novel algorithm of incremental speaker adaptation (ISA) based on universal background model (UBM) for saving storage and real-time processing. This algorithm can be seen as an extension of traditional speaker adaptation. It consists of two steps, adaptation and combination. It not only considers the speaker's characteristics in limited training data, but also prohibits over-fitting of the updated model. The incremental adaptation algorithm needs little storage and meets the requirement of real-time processing. In order to evaluate the efficiency and effectivity of the proposed approach, a real-time speaker segmentation system for broadcasting news is built. Experiment results demonstrate that our approach yields real time operation and achieves satisfactory performance.
15785287
A Nonlinear Multigrid Method for Total Variation Minimization from Image Restoration
Abstract
Image restoration has been an active research topic and variational formulations are particularly effective in high quality recovery. Although there exist many modelling and theoretical results, available iterative solvers are not yet robust in solving such modeling equations. Recent attempts on developing optimisation multigrid methods have been based on first order conditions. Different from this idea, this paper proposes to use piecewise linear function spanned subspace correction to design a multilevel method for directly solving the total variation minimisation. Our method appears to be more robust than the primal-dual method (Chan et al., SIAM J. Sci. Comput. 20(6), 1964–1977, 1999) previously found reliable. Supporting numerical results are presented.

15381679
A Modular Neural Network Architecture for Pattern Classification Based on Different Feature Sets
We propose a novel connectionist method for the use of different feature sets in pattern classification. Unlike traditional methods, e.g., combination of multiple classifiers and use of a composite feature set, our method copes with the problem based on an idea of soft competition on different feature sets developed in our earlier work. An alternative modular neural network architecture is proposed to provide a more effective implementation of soft competition on different feature sets. The proposed architecture is interpreted as a generalized finite mixture model and, therefore, parameter estimation is treated as a maximum likelihood problem. An EM algorithm is derived for parameter estimation and, moreover, a model selection method is proposed to fit the proposed architecture to a specific problem. Comparative results are presented for the real world problem of speaker identification.