Source author record

Sankar Veeramoni

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Computer Science and Game Theory Computer Vision Data Structures and Algorithms Discrete Mathematics Multiagent Systems

Catalog footprint

Research overview

3works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Computing Consensus Curves

We consider the problem of extracting accurate average ant trajectories from many (possibly inaccurate) input trajectories contributed by citizen scientists. Although there are many generic software tools for motion tracking and specific ones for insect tracking, even untrained humans are much better at this task, provided a robust method to computing the average trajectories. We implemented and tested several local (one ant at a time) and global (all ants together) method. Our best performing algorithm uses a novel global method, based on finding edge-disjoint paths in an ant-interaction graph constructed from the input trajectories. The underlying optimization problem is a new and interesting variant of network flow. Even though the problem is NP-hard, we implemented two heuristics, which work very well in practice, outperforming all other approaches, including the best automated system.

preprint2014arXiv

The Maximum k-Differential Coloring Problem

Given an $n$ -vertex graph $G$ and two positive integers $d,k \in \mathbb{N}$ , the ( $d,kn$ )-differential coloring problem asks for a coloring of the vertices of $G$ (if one exists) with distinct numbers from 1 to $kn$ (treated as \emph{colors}), such that the minimum difference between the two colors of any adjacent vertices is at least $d$ . While it was known that the problem of determining whether a general graph is ( $2,n$ )-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit ( $2,kn$ )-differential colorings. For practical reasons, we consider also color ranges larger than $n$ , i.e., $k > 1$ . We show that it is NP-complete to determine whether a graph admits a ( $3,2n$ )-differential coloring. The same negative result holds for the ( $\lfloor 2n/3 \rfloor, 2n$ -differential coloring problem, even in the case where the input graph is planar.

preprint2012arXiv

Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

Given a set of $n$ terminals, which are points in $d$ -dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pair's Manhattan distance. Even for $d=2$ , the problem is NP-hard, but constant-factor approximations are known. For $d \ge 3$ , the problem is APX-hard; it is known to admit, for any $\eps > 0$, an $O(n^\eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(\log^{d+1} n)$ -approximation algorithm for GMMN (and, hence, MMN) in $d \ge 2$ dimensions and an $O(\log n)$ -approximation algorithm for 2D. We show that an existing $O(\log n)$ -approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.