Randeep Bhatia

TCS Journal 2003 Journal Article

Asymptotically optimal declustering schemes for 2-dim range queries

• Rakesh K. Sinha
• Randeep Bhatia
• Chung-Min Chen

SODA Conference 2000 Conference Paper

On local search and placement of meters in networks

• Samir Khuller
• Randeep Bhatia
• Robert Pless

AAAI Conference 1999 Conference Paper

A Policy Description Language

• Jorge Lobo
• Randeep Bhatia
• Shamim Naqvi
• Bell Labs

Apolicy describesprinciples or strategies for a plan of action designedto achieve a particular set of goals. We define a policy as a functionthat maps a series of events into a set of actions. In this paperweintroduceP~D£, a simplebut expressivelanguageto specify policies. The design of the languagehas beenstrongly influenced by the action languages of Geffner and Bonet (Geffner Boner1998)and Gelfondand Lifschitz (Gelfond&Lifschitz 1993) and the compositetemporal event language of Motakis and Zaniolo (Motakis &Zaniolo 1997). The semantics is founded on recent results on formal descriptions of action theories based on automata and their application to active databases. Wesummarize somecomplexity results on the hardness of evaluating polices and briefly describe the implementationof a policy server being used to provide centralized administration of a soft switch in a communication network.

SODA Conference 1999 Conference Paper

The Full Degree Spanning Tree Problem

• Randeep Bhatia
• Samir Khuller
• Robert Pless
• Yoram J. Sussmann

SODA Conference 1998 Conference Paper

Minimizing Service and Operation Costs of Periodic Scheduling (Extended Abstract)

• Amotz Bar-Noy
• Randeep Bhatia
• Joseph Naor
• Baruch Schieber

FOCS Conference 1995 Conference Paper

The Loading Time Scheduling Problem (Extended Abstract)

• Randeep Bhatia
• Samir Khuller
• Joseph Naor

In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the shortest common supersequence problem. We use the same algorithmic technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines, and for the weighted shortest common supersequence problem.