Energy-Efficient Shortest Path Algorithms for Convergecast in Sensor Networks (2009)
Augustine, John, Han, Qi, Loden, Philip, Lodha, Sachin, Roy, Sasanka
We introduce a variant of the capacitated vehicle routing problem that is encountered in sensor networks for scientific data collection. Consider an undirected graph $G=(V \cup \{\mathbf{sink}\},E)$....
A Minimum Variance Method for Problems in Radio Antenna Placement (2009)
Rao, M. V. Panduranga, Ahuja, Amrit Lal, Iyengar, Srinivasan, Lodha, Sachin, Iyer, Kavita, Khade, Ranu, ...
Aperture synthesis radio telescopes generate images of celestial bodies from data obtained from several radio antennas. Placement of these antennas has always been a source of interesting problems....
Approximation Algorithms for Shortest Descending Paths in Terrains (2008)
Ahmed, Mustaq, Das, Sandip, Lodha, Sachin, Lubiw, Anna, Maheshwari, Anil, Roy, Sasanka
A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to find a shortest...
Covering Codes for Hats-on-a-line (2008)
Sarang Aravamuthan, Sachin Lodha
We consider a popular game puzzle, called Hats-on-a-line, wherein a warden has n prisoners, each one wearing a randomly assigned black or white hat, stand in a line. Thus each prisoner can see the...
1 THE GRAHAM-KNOWLTON PROBLEM REVISITED (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late ¢ ¡ ’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest...
The Graham-Knowlton Problem Revisited ⋆ (2008)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
Abstract. In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the...
Approximate Shortest Descent Path on a Terrain (2008)
Sasanka Roy, Sachin Lodha, Ip Das, Anil Maheshwari
A path from a point s to a point t on the surface of a polyhedral terrain is said to be descent if for every pair of points p = (x(p),y(p),z(p)) and q = (x(q),y(q),z(q)) on the path, if dist(s,p)...
Sachin Lodha, Tata Consultancy Services
In this age of globalization, organizations need to publish their micro-data owing to legal directives or share it with business associates in order to remain competitive. This puts personal privacy...
= N = N(A) (global condition). By the Lovasz Local Lemma (L.L.L.), if D (2007)
be an n-uniform hypergraph. Assume that the
Algorithms for Efficient Filtering in Content-Based Multicast (2007)
Stefan Langerman, Sachin Lodha, Rahul Shah
Abstract. Content-Based Multicast is a type of multicast where the source sends a set of different classes of information and not all the subscribers in the multicast group need all the information....
Tight Bound for the Density of Sequence of Integers the Sum of No Two of which is a (2007)
Perfect Square, Ayman Khalfalah, Sachin Lodha, Endre Szemeredi
P. Erdos and D. Silverman [EG-80] proposed the problem of determining the maximal density attainable by a set S of positive integers having the property that no two distinct elements of S sum up to a...
We present an optimal on-line algorithm for the List Update Problem when the request sequence has some particular structure.
List Update Problem by Bela Csaba (2007)
We present an optimal on-line algorithm for the List Update Problem when the request sequence has some particular structure.
Tight Bound for the Density of Sequence of Integers the Sum of No Two of which is a (2007)
Perfect Square, Ayman Khalfalah, Sachin Lodha, Endre Szemeredi
P. Erdos and D. Silverman [EG-80] proposed the problem of determining the maximal density attainable by a set S of positive integers having the property that no two distinct elements of S sum up to a...
Algorithms for E#cient Filtering in Content-Based Multicast (2007)
Stefan Langerman, Sachin Lodha, Rahul Shah
Abstract. Content-Based Multicast is a type of multicast where the source sends a set of di#erent classes of information and not all the subscribers in the multicast group need all the information....
The Average Transmission Overhead for Broadcast Encryption (2006)
Sarang Aravamuthan And, Sarang Aravamuthan, Sachin Lodha
We consider broadcast encryption schemes wherein a center needs to broadcast a secret message to a privileged set of receivers. We prescribe a probability distribution on the privileged set.
The Graham-Knowlton Problem Revisited (2004)
Navin Goyal, Sachin Lodha, S. Muthukrishnan
In late 60’s, Graham and Knowlton introduced the WIP (wire identification problem) that affected electricians: match the wires in the ceiling to those in the basement while making the fewest trips....
Abstract. The k–server problem is one of the most important and well studied problems in the area of online computation. Its importance stems from the fact that it models many practical problems...
We give a O(n 2
Fast digital identity revocation (extended abstract (1998)
William Aiello, Sachin Lodha, Rafail Ostrovsky
author visited Bellcore, also partially supported by DIMACS. 3
Fast digital identity revocation (extended abstract (1998)
William Aiello, Sachin Lodha, Rafail Ostrovsky
Abstract. The availability of fast and reliable Digital Identities is an essential ingredient for the successful implementation of the public-key infrastructure of the Internet. All digital identity...