Source author record

Sanjiv Kapoor

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity Computer Science and Game Theory

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

ANN queries: covering Voronoi diagram with hyperboxes

Given a set $S$ of $n$ points in $d$ -dimensional Euclidean metric space $X$ and a small positive real number $ε$ , we present an algorithm to preprocess $S$ and answer queries that require finding a set $S' \subseteq S$ of $ε$ -approximate nearest neighbors (ANNs) to a given query point $q \in X$ . The following are the characteristics of points belonging to set $S'$ : - $\forall s \in S'$ , $\exists$ a point $p \in X$ such that $|pq| \le ε$ and the nearest neighbor of $p$ is $s$ , and - $\exists$ a $s' \in S'$ such that $s'$ is a nearest neighbor of $q$ . During the preprocessing phase, from the Voronoi diagram of $S$ we construct a set of box trees of size $O(4^d\frac{V}δ(\fracπε)^{d-1})$ which facilitate in querying ANNs of any input query point in $O(\frac{1}{d}lg \frac{V}δ + (\fracπε)^{d-1})$ time. Here $δ$ equals to $(\fracε{2\sqrt{d}})^d$ , and $V$ is the volume of a large bounding box that contains all the points of set $S$ . The average case cardinality of $S'$ is shown to rely on $S$ and $ε$ .

preprint2013arXiv

Approximating Quadratic 0-1 Programming via SOCP

We consider the problem of approximating Quadratic O-1 Integer Programs with bounded number of constraints and non-negative constraint matrix entries, which we term as PIQP. We describe and analyze a randomized algorithm based on a program with hyperbolic constraints (a Second-Order Cone Programming -SOCP- formulation) that achieves an approximation ratio of $O(a_{max} \frac{n}{β(n)})$ , where $a_{max}$ is the maximum size of an entry in the constraint matrix and $β(n) \leq \min_i{W_i}$ , where $W_i$ are the constant terms that define the constraint inequalities. We note that by appropriately choosing $β(n)$ the randomized algorithm, when combined with other algorithms that achieve good approximations for smaller values of $W_i$ , allows better algorithms for the complete range of $W_i$ . This, together with a greedy algorithm, provides a $O^*(a_{max} n^{1/2} )$ factor approximation, where $O^*$ hides logarithmic terms. Our solution is achieved by a randomization of the optimal solution to the relaxed version of the hyperbolic program. We show that this solution provides the approximation bounds using concentration bounds provided by Chernoff-Hoeffding and Kim-Vu.

preprint2013arXiv

Auction Algorithm for Production Models

We show an auction-based algorithm to compute market equilibrium prices in a production model, where consumers purchase items under separable nonlinear utility concave functions which satisfy W.G.S(Weak Gross Substitutes); producers produce items with multiple linear production constraints. Our algorithm differs from previous approaches in that the prices are allowed to both increase and decrease to handle changes in the production. This provides a t^atonnement style algorithm which converges and provides a PTAS. The algorithm can also be extended to arbitrary convex production regions and the Arrow-Debreu model. The convergence is dependent on the behavior of the marginal utility of the concave function.

preprint2013arXiv

Efficient Construction of Spanners in $d$ -Dimensions

In this paper we consider the problem of efficiently constructing $k$ -vertex fault-tolerant geometric $t$ -spanners in $\dspace$ (for $k \ge 0$ and $t >1$ ). Vertex fault-tolerant spanners were introduced by Levcopoulus et. al in 1998. For $k=0$ , we present an $O(n \log n)$ method using the algebraic computation tree model to find a $t$ -spanner with degree bound O(1) and weight $O(\weight(MST))$. This resolves an open problem. For $k \ge 1$ , we present an efficient method that, given $n$ points in $\dspace$, constructs $k$ -vertex fault-tolerant $t$ -spanners with the maximum degree bound O(k) and weight bound $O(k^2 \weight(MST))$ in time $O(n \log n)$ . Our method achieves the best possible bounds on degree, total edge length, and the time complexity, and solves the open problem of efficient construction of (fault-tolerant) $t$ -spanners in $\dspace$ in time $O(n \log n)$ .

preprint2010arXiv

A near optimal algorithm for finding Euclidean shortest path in polygonal domain

We present an algorithm to find an {\it Euclidean Shortest Path} from a source vertex $s$ to a sink vertex $t$ in the presence of obstacles in $\Re^2$ . Our algorithm takes $O(T+m(\lg{m})(\lg{n}))$ time and $O(n)$ space. Here, $O(T)$ is the time to triangulate the polygonal region, $m$ is the number of obstacles, and $n$ is the number of vertices. This bound is close to the known lower bound of $O(n+m\lg{m})$ time and $O(n)$ space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest.

preprint2010arXiv

Approximate Shortest Path through a Weighted Planar Subdivision

This paper presents an approximation algorithm for finding a shortest path between two points $s$ and $t$ in a weighted planar subdivision $\PS$. Each face $f$ of $\PS$ is associated with a weight $w_f$ , and the cost of travel along a line segment on $f$ is $w_f$ multiplied by the Euclidean norm of that line segment. The cost of a path which traverses across several faces of the subdivision is the sum of the costs of travel along each face. Our algorithm progreeses the discretized shortest path wavefront from source $s$ , and takes polynomial time in finding an $ε$ -approximate shortest path.

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.

Sanjiv Kapoor

Research overview

Is this your work?

6 publications

ANN queries: covering Voronoi diagram with hyperboxes

Approximating Quadratic 0-1 Programming via SOCP

Auction Algorithm for Production Models

Efficient Construction of Spanners in $d$ -Dimensions

A near optimal algorithm for finding Euclidean shortest path in polygonal domain

Approximate Shortest Path through a Weighted Planar Subdivision

See the researcher in context

Building this map preview

Sanjiv Kapoor

Research overview

Is this your work?

6 publications

ANN queries: covering Voronoi diagram with hyperboxes

Approximating Quadratic 0-1 Programming via SOCP

Auction Algorithm for Production Models

Efficient Construction of Spanners in ddd-Dimensions

A near optimal algorithm for finding Euclidean shortest path in polygonal domain

Approximate Shortest Path through a Weighted Planar Subdivision

See the researcher in context

Building this map preview

Efficient Construction of Spanners in $d$ -Dimensions