Data Migration on Parallel Disks: Algorithms and Evaluation (2009)
Leana Golubchik, Samir Khuller, Yoo-ah Kim, Svetlana Shargorodskaya, Justin Wan
Abstract. Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high...
On Broadcasting in Heterogenous Networks \Lambda (2009)
z Abstract In this paper we study a widely used broadcasting heuristic for heterogenous networks of workstations, called fastest node first. We show that this heuristic produces an optimal solution...
Algorithms for Calculating Statistical Properties of Moving Points (2009)
Sorelle A. Friedler, William Gasarch, Samir Khuller, Amitabh Varshney
Robust statistics and kinetic data structures are two frequently studied theoretical areas with practical motivations. The former topic is the study of statistical estimators that are robust to data...
Minimizing Communication Cost in Distributed Multi-query Processing (2009)
Jian Li, Amol Deshp, Samir Khuller
Abstract — Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the...
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity (2009)
Richard Matthew Mccutchen, Samir Khuller
Abstract. Clustering is a common problem in the analysis of large data sets. Streaming algorithms, which make a single pass over the data set using small working memory and produce a clustering...
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity (2009)
Richard Matthew Mccutchen, Samir Khuller
Abstract. Clustering is a common problem in the analysis of large data sets. Streaming algorithms, which make a single pass over the data set using small working memory and produce a clustering...
An Optimal Incremental Algorithm for Minimizing Lateness with Rejection (2009)
Abstract. This paper re-examines the classical problem of minimizing maximum lateness which is defined as follows: given a collection of n jobs with processing times and due dates, in what order...
Energy Efficient Monitoring in Sensor Networks ⋆ (2009)
Amol Deshp, Samir Khuller, Azarakhsh Malekian, Mohammed Toossi
Abstract. In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem...
Abstract Our work was motivated by the problem of managing data on storage devices, typically a set of parallel disks. Due to dynamic changes in load, one needs to develop algorithms for quickly...
On Computing Compression Trees for Data Collection in Sensor Networks (2009)
Li, Jian, Deshpande, Amol, Khuller, Samir
We address the problem of efficiently gathering correlated data from a wired or a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding...
Minimizing Communication Cost in Distributed Multi-query Processing (2009)
Jian Li, Amol Deshp, Samir Khuller
Abstract — Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the...
Data Migration on Parallel Disks: Algorithms and Evaluation � (2009)
Leana Golubchik, Samir Khuller, Yoo-ah Kim, Svetlana Shargorodskaya, Justin Wan
Abstract. Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high...
Some Open Problems in Computational Molecular Biology (2008)
Samir Khuller, Tao Jiang, Paul Kearney, Ming Li
This column will carry problems arising in the design of algorithms for discrete optimization problems. Problems are solicited in all areas of algorithm design that are covered by the Journal of...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Abstract. In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph G = (V, E), the goal is to cover all the edges by picking...
A Performance Study of Bistro, a Scalable Upload Architecture (2008)
William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller
Hot spots are a major obstacle to achieving scalability in the Internet. We have observed that the existence of hot spots in upload applications (whose examples include submission of income tax forms...
Samir Khuller, Balaji Raghavachari, Neal Young
Designing multi-commodity flow trees
Richard Matthew Mccutchen, Dr. Samir Khuller, Richard Matthew Mccutchen
One of the most common administrative tasks that organizations perform is the assignment of people to positions based on the people’s preferences. A computer program that chooses an assignment...
Fast Reconfiguration of Data Placement in Parallel Disks ∗ (2008)
Srinivas Kashyap, Samir Khuller
The “How much information? ” study produced by the school of information management and systems at the University of California at Berkeley [10], estimates that about 5 exabytes of new...
Finding Most Probable Worlds of Probabilistic Logic Programs (2008)
Samir Khuller, Vanina Martinez, Dana Nau, Gerardo Simari, Amy Sliva, V. S. Subrahmanian
Abstract. Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a...
Approximation Algorithms for Channel Allocation Problems in Broadcast Networks (2008)
Rajiv G, Samir Khuller, Aravind Srinivasan, Nan Wang
Abstract. We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered...
Achieving Anonymity via Clustering (2008)
Gagan Aggrawal, Samir Khuller, Tomás Feder, Rina Panigrahy, An Zhu
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Integrated Topology Control and Routing in Wireless Optical Mesh Networks* (2008)
Abhishek Kashyap, Kwangil Lee, Mehdi Kalantari, Samir Khuller, Mark Shayman
Abstract — We study the problem of integrated topology control and routing in Free Space Optical (FSO) mesh backbone networks. FSO links are high-bandwidth, low interference links that can be...
Government at all levels is a major collector and provider of data. (2008)
Leana Golubchik, Samir Khuller, William C. Cheng, Hanan Samet, Cheng-fu Chou
In this project we focus on the collection of data over wide-area networks and address the scalability issues which arise in the context of Internet-based massive data collection applications....
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (Extended Abstract) (2008)
Rajiv G, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Finding Most Probable Worlds of Probabilistic Logic Programs (2008)
Samir Khuller, Vanina Martinez, Dana Nau, Gerardo Simari, Amy Sliva, V. S. Subrahmanian
Abstract. Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a...
Fast Reconfiguration of Data Placement in Parallel Disks ∗ (2008)
Srinivas Kashyap, Samir Khuller, Leana Golubchik
The “How much information? ” study produced by the school of information management and systems at the University of California at Berkeley [10], estimates that about 5 exabytes of new...
Abstract Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers, or multimedia servers for...
Abstract Algorithms for Facility Location Problems with Outliers (Extended Abstract) (2008)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
On Generalized Gossiping and Broadcasting (Extended Abstract) (2008)
Samir Khuller, Yoo-ah Kim, Yung-Chun (Justin) Wan
Samir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742.
Randeep Bhatia, Samir Khuller, Robert Pless, Yoram J. Sussmann
The full degree spanning tree problem is defined as follows: given a connected graph G = (V; E) find a spanning tree T so as to maximize the number of vertices whose degree in T is the same as in G...
Localizing an Object With Finger Probes (2007)
Robert Freimer Samir, Samir Khuller, Christine Piatko, Kathleen Romanik, Diane Souvaine
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Bistro: a Framework for Building Scalable Wide-Area Upload Applications (2007)
Samrat Bhattacharjee, William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller
Hot spots are a major obstacle to achieving scalability in the Internet. At the application layer, hot spots are usually caused by either (a) high demand for some data or (b) high demand for a...
A network-flow technique for finding low-weight bounded-degree trees (2007)
Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
The Loading Time Scheduling Problem (Extended Abstract) (2007)
Randeep Bhatia, Samir Khuller, Joseph (seffi Naor
) Randeep Bhatia Samir Khuller y Joseph (Seffi) Naor z Computer Science Department Computer Science Department Computer Science Department Univ. of Maryland Univ. of Maryland Technion College Park,...
The Loading Time Scheduling Problem (2007)
Extend Ed, Randeep Bhatia, Samir Khuller, Joseph (seffi Naor
) Randeep Bhatia Samir Khuller y Joseph (Seffi) Naor z Computer Science Department Computer Science Department Computer Science Department Univ. of Maryland Univ. of Maryland Technion College Park,...
On the Parallel Complexity of Digraph Reachability (2007)
We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these...
Dependent Rounding in Bipartite Graphs Rajiv Gandhi (2007)
Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
We combine the pipage rounding technique of Ageev & Sviridenko witha recent rounding method developed by Srinivasan, to develop a new randomized rounding approach for fractional vectors defined...
1 Construction of an Efficient Overlay Multicast Infrastructure for Real-time Applications (2007)
Suman Banerjee, Christopher Kommareddy, Koushik Kar, Bobby Bhattacharjee, Samir Khuller
Abstract---We consider an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are...
Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann
Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a...
These are my lecture notes from CMSC 651: Design and Analysis of Algorithms, a one semester course that I taught at University of Maryland in the Spring of 1995. The course covers core material in...
Randeep Bhatia, Samir Khuller, Joseph (seffi 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...
Samir Khuller, Balaji Raghavachari, Neal Young
Abstract. Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem...
Samir Khuller, Aravind Srinivasan
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Samir Khuller, Robert Pless, Yoram J. Sussmann
The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
Samir Khuller, Balaji Raghavachari, Neal Young
The MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the...
Alok Aggarwal, Amotz Bar-noy, Samir Khuller, Dina Kravets, Baruch Schieber
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Sinks [ Sources; Sinks 2 Sources), where jSinksj = n,...
Samir Khuller, Balaji Raghavachari, Neal Young
Abstract. The MEG (minimum equivalent graph) problem is the following: "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between...
Samir Khuller, Balaji Raghavachari, Azriel Rosenfeld
Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a "graph space". The...
1 A Clustering Scheme for Hierarchical Control in Multi-hop Wireless Networks (2007)
Abstract---In this paper we present a clustering scheme to create a hierarchical control structure for multi-hop wireless networks. A cluster is defined as a subset of vertices, whose induced graph...
Abstract. The MEG (minimum equivalent graph) problem is the following: "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between...
Samir Khuller, Balaji Raghavachari, Neal Young
We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the two...
We give an efficient deterministic parallel approximation algorithm for the minimumweight vertex- and set-cover problems and their duals (edge/element packing). The algorithm is simple and suitable...
Samir Khuller, Balaji Raghavachari, Neal Young
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the...
(c) 1996 SIAM J. Computing LOW DEGREE SPANNING TREES OF SMALL WEIGHT (2007)
Samir Khuller, Balaji Raghavachari, Neal Young
Abstract. Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem...
Bistro: a Framework for Building Scalable Wide-Area Upload (2007)
Applications Samrat Bhattacharjee, Samrat Bhattacharjee, William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller
in the Internet. At the application layer, hot spots are usually caused by either (a) high demand for some data or (b) high demand for a certain service. This high demand for data or services, is...
An Improved Approximation Algorithm for Vertex Cover with Hard Capacities (Extended Abstract) (2007)
Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
Rajiv Gandhi , Eran Halperin , Samir Khuller , Guy Kortsarz , and Aravind Srinivasan Department of Computer Science, University of Maryland, College Park, MD 20742. Research supported by NSF Award...
Leana Golubchik, Samir Khuller, Yoo-ah Kim
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high demand for...
Khuller, Samir, Raschid, Louiqa, Wu, Yao
There are abundance of web accessible life science sources. Traversal of a particular path can answer a navigational query, returning a target object set (TOS). The cardinality of TOS is considered...
Khuller, Samir, Raschid, Louiqa, Wu, Yao
There are abundance of web accessible life science sources. Traversal of a particular path can answer a navigational query, returning a target object set (TOS). The cardinality of TOS is considered...
Relay Placement Approximation Algorithms for k-Connectivity in Wireless Sensor Networks (2006)
Kashyap, Abhishek, Khuller, Samir, Shayman, Mark
Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some...
Dependent rounding and its applications to approximation algorithms (2006)
Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
Abstract We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading...
Dependent rounding and its applications to approximation algorithms (2006)
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to...
Achieving Anonymity via Clustering (2006)
Gagan Aggarwal, Samir Khuller, Tomás Feder
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Achieving Anonymity via Clustering (2006)
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying...
Query planning in the presence of overlapping sources (2006)
Jens Bleiholder, Samir Khuller, Felix Naumann, Louiqa Raschid, Yao Wu
Abstract. Navigational queries on Web-accessible life science sources pose unique query optimization challenges. The objects in these sources are interconnected to objects in other sources, forming a...
To Fill or not to Fill: The Gas Station Problem (2006)
Samir Khuller, Azarakhsh Malekian, Julián Mestre
In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem. We consider a more general model that incorporates the actual cost in terms of gas...
To Fill or not to Fill: The Gas Station Problem (2006)
Samir Khuller, Azarakhsh Malekian
(Extended Abstract)?
To Fill or not to Fill: The Gas Station Problem (2006)
In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem. We consider a more general model that incorporates the actual cost in terms of gas...
Khuller, Samir, Raschid, Louiqa, Wu, Yao
There are abundance of web accessible life science sources. Traversal of a particular path can answer a navigational query, returning a target object set (TOS). The cardinality of TOS is considered...
Khuller, Samir, Raschid, Louiqa, Wu, Yao
There are abundance of web accessible life science sources. Traversal of a particular path can answer a navigational query, returning a target object set (TOS). The cardinality of TOS is considered...
Efficient and Resilient Backbones for Multihop Wireless Networks (2005)
Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Samir Khuller
Abstract — We consider the problem of finding “backbones” in multihop wireless networks. The backbone provides end-toend connectivity, allowing non-backbone nodes to save energy since they do...
Efficient and Resilient Backbones for Multihop Wireless Networks (2005)
Seungjoon Lee, Bobby Bhattacharjee, Aravind Srinivasan, Samir Khuller
Abstract — We consider the problem of finding “backbones” in mobile ad-hoc networks. The backbone provides end-to-end connectivity, allowing non-backbone nodes to save energy since they do not...
On degree constrained shortest paths (2005)
Abstract. Traditional shortest path problems play a central role in both the design and use of communication networks and have been studied extensively. In this work, we consider a variant of the...
Approximation Algorithms for Partial Covering Problems (2004)
Rajiv Gandhi, Samir Khuller, Aravind Srinivasan
We study a generalization of covering problems called partial covering . Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems....
Approximation Schemes for Broadcasting in Heterogeneous Networks, Samir Khuller, Yoo-Ah (2004)
Samir Khuller, Yoo-ah Kim, Gerhard Woeginger
Abstract. We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor Ô � has transmission time Ø�, which is the time taken to send a message to...
Data Migration on Parallel Disks (2003)
Golubchik, Leana, Khuller, Samir, Kim, Yoo-Ah, Shargorodskaya, Svetlana, Wan, Yung-Chun (Justin)
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers or multimedia servers, for handling high...
Data Migration on Parallel Disks (2003)
Golubchik, Leana, Khuller, Samir, Kim, Yoo-Ah, Shargorodskaya, Svetlana, Wan, Yung-Chun (Justin)
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers or multimedia servers, for handling high...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (2003)
Gandhi, Rajiv, Halperin, Eran, Khuller, Samir, Kortsarz, Guy, Srinivasan, Aravind
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum...
An Improved Approximation Algorithm For Vertex Cover with Hard Capacities (2003)
Gandhi, Rajiv, Halperin, Eran, Khuller, Samir, Kortsarz, Guy, Srinivasan, Aravind
In this paper we study the capacitated vertex cover problem, a generalization of the well-known vertex cover problem. Given a graph $G=(V,E)$, the goal is to cover all the edges by picking a minimum...
On Generalized Gossiping and Broadcasting (2003)
Abstract. The problems of gossiping and broadcasting have been widely studied. The basic gossip problem is defined as follows: there are n individuals, with each individual having an item of gossip....
www.elsevier.com/locate/jalgor On generalized gossiping and broadcasting ✩ (2003)
The problems of gossiping and broadcasting have been widely studied. The basic gossip problem is defined as follows: there are n individuals, with each individual having an item of gossip. The goal...
Large-scale Data Collection: a Coordinated Approach (2003)
William C. Cheng, Samir Khuller, Cheng-fu Chou
Abstract — In this paper we consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion...
Construction of an efficient overlay multicast infrastructure for real-time applications (2003)
Suman Banerjee, Christopher Kommareddy, Koushik Kar, Bobby Bhattacharjee, Samir Khuller
Abstract — We consider an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs...
Algorithms for Non-Uniform Size Data Placement on Parallel Disks (2003)
Srinivas Kashyap, Samir Khuller
We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data items) that need to be assigned...
Algorithms for Data Migration with Cloning (2003)
Samir Khuller, Yoo-Ah Kim, Yung-Chun (Justin) Wan
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers, or multimedia servers for handling high...
Algorithms for Non-Uniform Size Data Placement on Parallel Disks (2003)
Srinivas Kashyap, Samir Khuller
at least k\Gamma \Delta k+\Delta
Large-scale Data Collection: a Coordinated Approach (2003)
William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller, Yung-Chun (Justin) Wan
In this paper we consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the paths...
Algorithms for Data Migration with Cloning (2003)
Samir Khuller, Yoo-ah Kim, Yung-Chun (Justin) Wan
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high demand storage servers are used as web servers, or multimedia servers for handling high...
On Generalized Gossiping and Broadcasting (2003)
The problems of gossiping and broadcasting have been widely studied. The basic gossip problem is de ned as follows: there are n individuals, with each individual having an item of gossip. The goal is...
Large-scale Data Collection: a Coordinated Approach (2003)
William C. Cheng, Samir Khuller, Cheng-fu Chou
Abstract — In this paper we consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion...
Construction of an efficient overlay multicast infrastructure for real-time applications (2003)
Suman Banerjee, Christopher Kommareddy, Koushik Kar, Bobby Bhattacharjee, Samir Khuller
Abstract—We consider an overlay architecture where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs are...
Algorithms for Data Migration with Cloning (2003)
Abstract. Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such high-demand storage servers are used as Web servers or as multimedia servers for...
Construction of an efficient overlay multicast infrastructure for real-time applications (2003)
Suman Banerjee, Christopher Kommareddy, Koushik Kar, Bobby Bhattacharjee, Samir Khuller
We consider an overlay architecture (called OMNI) where service providers deploy a set of service nodes (called MSNs) in the network to efficiently implement media-streaming applications. These MSNs...
Large-scale Data Collection: a Coordinated Approach (2003)
William C. Cheng, Samir Khuller, Cheng-fu Chou
Abstract — In this paper we consider the problem of collecting a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion...
A Performance Study of a Large-scale Data Collection Problem (2002)
Chou, Cheng-Fu, Wan, Yung-Chun (Justin), Cheng, William C., Golubchik, Leana, Khuller, Samir
In this paper, we consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This...
A Performance Study of a Large-scale Data Collection Problem (2002)
Chou, Cheng-Fu, Wan, Yung-Chun (Justin), Cheng, William C., Golubchik, Leana, Khuller, Samir
In this paper, we consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This...
Designing Multi-Commodity Flow Trees (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the...
Approximating the Minimum Equivalent Digraph (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper...
Low-Degree Spanning Trees of Small Weight (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-known Christofides...
Balancing Minimum Spanning and Shortest Path Trees (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal E.
This paper give a simple linear-time algorithm that, given a weighted digraph, finds a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm...
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover (2002)
Khuller, Samir, Vishkin, Uzi, Young, Neal
The paper describes a simple deterministic parallel/distributed (2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem and its dual (edge/element packing).
On Strongly Connected Digraphs with Bounded Cycle Length (2002)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper...
On a Graph-theoretic Approach to Scheduling Large-scale Data Transfers (2002)
Cheng, William C., Chou, Cheng-Fu, Golubchik, Leana, Khuller, Samir, Wan, Yungchun (Justin)
In this paper we consider the problem of moving a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of...
On a Graph-theoretic Approach to Scheduling Large-scale Data Transfers (2002)
Cheng, William C., Chou, Cheng-Fu, Golubchik, Leana, Khuller, Samir, Wan, Yungchun (Justin)
In this paper we consider the problem of moving a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of...
On a graph-theoretic approach to scheduling large-scale data transfers (2002)
William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller, Yungchun (justin Wan
In this paper we consider the problem of moving a large amount of data from several dierent hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of...
Algorithms for Minimizing Response Time in Broadcast Scheduling (2002)
Rajiv Gandhi, Samir Khuller, Yoo-ah Kim, Yung-Chun (Justin) Wan
In this paper we study the following problem. There are n pages which clients can request at any time. The arrival times of requests for pages are known. Several requests for the same page may arrive...
A Performance Study of a Large-scale Data Collection Problem (2002)
William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller
We consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This problem is...
On Directed Steiner Trees (2002)
Leonid Zosin Samir, Samir Khuller
The directed Steiner tree problem is the following: given a directed graph G = (V; E) with weights on the edges, a set of terminals S ` V , and a root vertex r, find a minimum weight out-branching T...
Capacitated Vertex Covering with Applications (2002)
Sudipto Guha Refael, Sudipto Guha, Refael Hassin, Samir Khuller
In this paper we study the capacitated vertex cover problem, a generalization of the well known vertex problem. Given a graph G = (V; E) with weights on the vertices, the goal is to cover all the...
A Performance Study of a Large-scale Data Collection Problem (2002)
Cheng-fu Chou, Yung-Chun (Justin) Wan, William C. Cheng, Leana Golubchik, Samir Khuller
We consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This problem is...
Algorithms for minimizing response time in broadcast scheduling (2002)
Abstract. In this paper we study the following problem. There are n pages which clients can request at any time. The arrival times of requests for pages are known. Several requests for the same page...
Approximation Algorithms for Partial Covering Problems (2001)
Gandhi, Rajiv, Khuller, Samir, Srinivasan, Aravind
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Approximation Algorithms for Partial Covering Problems (2001)
Gandhi, Rajiv, Khuller, Samir, Srinivasan, Aravind
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
A secure and scalable wide-area upload service (2001)
William C. Cheng, Cheng-fu Chou, Leana Golubchik, Samir Khuller
Abstract In a recent paper, we introduced a framework termed Bistro to facilitate the building of scalable wide-area upload applications. An example of an important upload application is the...
Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost...
A Clustering Scheme for Hierarchical Control in Wireless Networks (2001)
In this paper we present a clustering scheme to create a hierarchical control structure for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In...
A clustering scheme for hierarchical control in multi-hop wireless networks (2001)
Abstract---In this paper we present a clustering scheme to create a hierarchical control structure for multi-hop wireless networks. A cluster is defined as a subset of vertices, whose induced graph...
Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost...
Approximation algorithms for partial covering problems (2001)
Samir Khuller, Aravind Srinivasan
We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For...
Algorithms for facility location problems with outliers (2001)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
A Clustering Scheme for Hierarchical Control in Wireless Networks (2001)
Abstract---In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a...
Algorithms for facility location problems with outliers (2001)
Moses Charikar, Samir Khuller, David M. Mount, Giri Narasimhan
Facility location problems are traditionally investigated with the assumption that all the clients are to be provided service. A significant shortcoming of this formulation is that a few very distant...
A Clustering Scheme for Hierarchical Control in Wireless Networks (2001)
Abstract—In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a...
A Clustering Scheme for Hierarchical Routing in Wireless Networks (2000)
Banerjee, Suman, Khuller, Samir
In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a cluster is...
A Clustering Scheme for Hierarchical Routing in Wireless Networks (2000)
Banerjee, Suman, Khuller, Samir
In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a cluster is...
On local search and placement of meters in networks (2000)
Samir Khuller, Randeep Bhatia, Robert Pless
This work is motivated by the problem of placing pressure meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a...
A Clustering Scheme for Hierarchical Routing in Wireless Networks (2000)
In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a cluster is...
Centers Of Sets Of Pixels (2000)
Samir Khuller, Azriel Rosenfeld, Angela Y. Wu
The center of a connected graph G is the set of nodes of G for which the maximum distance to any other node of G is as small as possible. If G is a simply connected set of lattice points...
Nili Guttmann-beck, Refael Hassin, Samir Khuller, Balaji Raghavachari
Let G = (V; E) be a complete undirected graph with vertex set V , edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 ; : : : ; V k ....
Approximation Algorithms for Data Placement on Parallel Disks (2000)
Leana Golubchik, Sanjeev Khanna, Samir Khuller, An Zhu
Abstract. We study an optimization problem that arises in the context of data placement in a multimedia storage system. We are given a collection of M multimedia objects (data objects) that need to...
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets (1999)
A greedy approximation algorithm based on "spider decompositions " was developed by Klein and Ravi for node weighted Steiner trees. This algorithm provides a worst case...
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets (1999)
A greedy approximation algorithm based on "spider decompositions" was developed by Klein and Ravi for node weighted Steiner trees. This algorithm provides a worst case approximation ratio...
A Uniform Framework for Approximating Weighted Connectivity Problems (1999)
Samir Khuller, Balaji Raghavachari, An Zhu
We introduce a new algorithmic technique that applies to several graph connectivity problems. Its power is demonstrated by experimental studies of the minimum-weight strongly-connected spanning...
The Full Degree Spanning Tree Problem (1998)
Bhatia, Randeep, Khuller, Samir, Pless, Robert, Sussmann, Yoram
The full degree spanning tree problem is defined as follows: given a connected graph $G=(V,E)$ find a spanning tree $T$ so as to maximize the number of vertices whose degree in $T$ is the same as in...
The Full Degree Spanning Tree Problem (1998)
Bhatia, Randeep, Khuller, Samir, Pless, Robert, Sussmann, Yoram
The full degree spanning tree problem is defined as follows: given a connected graph $G=(V,E)$ find a spanning tree $T$ so as to maximize the number of vertices whose degree in $T$ is the same as in...
Graphbots: Cooperative Motion Planning in Discrete Spaces (1998)
Samir Khuller, Ehud Rivlin, Azriel Rosenfeld, Life Fellow
Abstract—Most previous theoretical work on motion planning for a group of robots has addressed the problem of path planning for the individual robots sequentially, in geometrically simple regions...
Algorithms for capacitated vehicle routing (1998)
Moses Charikar, Samir Khuller, Balaji Raghavachari
Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...
Greedy strikes back: Improved Facility Location Algorithms (1998)
A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are...
Algorithms for Capacitated Vehicle Routing (1998)
Moses Charikar, Samir Khuller, Balaji Raghavachari
Given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k...
Greedy strikes back: Improved Facility Location Algorithms (1998)
A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are...
Nili Guttmann-beck, Refael Hassin, Samir Khuller, Balaji Raghavachari
Let G = (V, E) be a complete undirected graph with vertex set V , edge set E, and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 , ..., V k . The...
The Full Degree Spanning Tree Problem (1998)
Randeep Bhatia, Samir Khuller, Robert Pless, Yoram J. Sussmann
this paper we study the problem of computing a spanning tree T in a connected graph G = (V; E) so as to maximize the number of vertices of full degree (FDST). These are vertices whose degree in the...
Facility Location with Dynamic Distance Functions (Extended Abstract) (1998)
Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann
) Randeep Bhatia Sudipto Guha y Samir Khuller z Yoram J. Sussmann x Dept. of Computer Science University of Maryland College Park, MD 20742 Abstract Facility location problems have always been...
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets (1997)
A greedy approximation algorithm based on ``spider decompositions'' was developed by Klein and Ravi for node weighted Steiner trees. This algorithm provides a worst case approximation ratio of $2 \ln...
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets (1997)
A greedy approximation algorithm based on ``spider decompositions'' was developed by Klein and Ravi for node weighted Steiner trees. This algorithm provides a worst case approximation ratio of $2 \ln...
Algorithms for Capacitated Vehicle Routing (1997)
Charikar, Moses, Khuller, Samir, Raghavachari, Balaji
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...
Algorithms for Capacitated Vehicle Routing (1997)
Charikar, Moses, Khuller, Samir, Raghavachari, Balaji
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at...
Facility Location with Dynamic Distance Functions (1997)
Bhatia, Randeep, Guha, Sudipto, Khuller, Samir, Sussmann, Yoram J.
Facility location problems have always been studied with the assumption that the edge lengths in the network are {\em static} and do not change over time. The underlying network could be used to...
Facility Location with Dynamic Distance Functions (1997)
Bhatia, Randeep, Guha, Sudipto, Khuller, Samir, Sussmann, Yoram J.
Facility location problems have always been studied with the assumption that the edge lengths in the network are {\em static} and do not change over time. The underlying network could be used to...
A network-flow technique for finding low-weight bounded-degree spanning trees (1997)
S'andor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young
4 z
A network-flow technique for finding low-weight bounded-degree spanning trees (1997)
S'andor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
A Network Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1997)
Sandor P. Fekete, S'andor P. Fekete, Samir Khuller, Samir Khuller, Monika Klemmstein, Monika Klemmstein, ...
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
Fault Tolerant K-Center Problems (1997)
Samir Khuller, Robert Pless, Yoram J. Sussmann
The basic K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
The Budgeted Maximum Coverage Problem (1997)
Samir Khuller, Anna Moss, Joseph (Seffi) Naor
The budgeted maximum coverage problem is: given a collection S of sets with associated costs defined over a domain of weighted elements, and a budget L, find a subset of S 0 ` S such that the total...
The Loading Time Scheduling Problem (1996)
Bhatia, Randeep, Khuller, Samir, Naor, Joseph (Seffi)
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...
The Capacitated K-Center Problem (1996)
Khuller, Samir, Sussmann, Yoram J.
The capacitated $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the...
Fault Tolerant K-Center Problems (1996)
Khuller, Samir, Pless, Robert, Sussmann, Yoram J.
The basic $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
Approximation Algorithms for Connected Dominating Sets (1996)
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to some node in...
The Loading Time Scheduling Problem (1996)
Bhatia, Randeep, Khuller, Samir, Naor, Joseph (Seffi)
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...
The Capacitated K-Center Problem (1996)
Khuller, Samir, Sussmann, Yoram J.
The capacitated $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the...
Fault Tolerant K-Center Problems (1996)
Khuller, Samir, Pless, Robert, Sussmann, Yoram J.
The basic $K$-center problem is a fundamental facility location problem, where we are asked to locate $K$ facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
Approximation Algorithms for Connected Dominating Sets (1996)
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to some node in...
The Capacitated K-Center Problem (1996)
Samir Khuller, Yoram J. Sussmann
The capacitated K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
Improved Approximation Algorithms for Uniform Connectivity Problems (1996)
Samir Khuller, Balaji Raghavachari
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...
On strongly connected digraphs with bounded cycle length (1996)
Samir Khuller, Balaji Raghavachari, Neal Young
Given a directed graph G = (V; E), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v, if there is a path from u to v in E, then there is a path...
Approximation Algorithms for Connected Dominating Sets (1996)
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to some node in...
Approximation Algorithms for Connected Dominating Sets (1996)
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in...
The Capacitated K-Center Problem (1996)
Samir Khuller, Yoram J. Sussmann
The capacitated K-center problem is a fundamental facility location problem, where we are asked to locate K facilities in a graph, and to assign vertices to facilities, so as to minimize the maximum...
Graph and Network Algorithms (1996)
Samir Khuller, Balaji Raghavachari
INTRODUCTION Graphs provide a powerful tool to model objects and relationships among objects. The study of graphs dates back to Euler 's days in the 18th century, when he defined the Konigsberg...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
The Complexity of Finding Most Vital Arcs and Nodes (1995)
Bar-Noy, Amotz, Khuller, Samir, Schieber, Baruch
Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs...
The Complexity of Finding Most Vital Arcs and Nodes (1995)
Bar-Noy, Amotz, Khuller, Samir, Schieber, Baruch
Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs...
Improved Approximation Algorthmsor Uniform Connectivity Problems (1995)
Khuller, Samir, Raghavachari, Balaji
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...
Improved Approximation Algorthmsor Uniform Connectivity Problems (1995)
Khuller, Samir, Raghavachari, Balaji
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...
Approximation Algorithms for Finding Highly Connected Subgraphs (1995)
(Also cross-referenced as UMIACS-TR-95-4)
Approximation Algorithms for Finding Highly Connected Subgraphs (1995)
(Also cross-referenced as UMIACS-TR-95-4)
Balancing Minimum Spanning Trees and Shortest-Path Trees (1995)
Samir Khuller, Balaji Raghavachari, Penn State, Neal Young
Abstract We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the...
Balancing Minimum Spanning Trees and Shortest-Path Trees (1995)
Abstract We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the...
The complexity of finding most vital arcs and nodes (1995)
Amotz Bar-noy, Samir Khuller, Baruch Schieber
Let G(V; E) be a graph (either directed or undirected) with a non-negative length `(e) associated with each arc e in E. For two specified nodes s and t in V, the k most vital arcs (or nodes) are...
Improved Approximation Algorithms for Uniform Connectivity Problems (1995)
Samir Khuller, Balaji Raghavachari
The problem of finding minimum weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Neal Young, Balaji Raghavachari, Balaji Raghavachari
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
BOUNDED-DEGREE TREES USING NETWORK FLOW 311 (1995)
Or P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young
pp. 105�117.
Localizing an object with finger probes (1994)
Freimer, Robert, Khuller, Samir, Mitchell, Joe, Piatko, Christine, Romanik, Kathleen, Souvaine, Diane
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Localizing an object with finger probes (1994)
Freimer, Robert, Khuller, Samir, Mitchell, Joe, Piatko, Christine, Romanik, Kathleen, Souvaine, Diane
We consider the problem of identifying one of a set of polygonal models in the plane using point probes and finger probes. In particular, we give strategies for using a minimum number of finger...
Khuller, Samir, Raghavachari, Balaji, Rosenfeld, Azriel
Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a ``graph space''. The robot can locate...
Khuller, Samir, Raghavachari, Balaji, Rosenfeld, Azriel
Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a ``graph space''. The robot can locate...
Low Degree Spanning Trees of Small Weight (1994)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of...
On Strongly Connected Digraphs with Bounded Cycle Length (1994)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the complexity of this...
Low Degree Spanning Trees of Small Weight (1994)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
Given n points in the plane, the degree-K spanning tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of...
On Strongly Connected Digraphs with Bounded Cycle Length (1994)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The MEG (minimum equivalent graph) problem is "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." We consider the complexity of this...
On-line algorithms for weighted bipartite matching and stable marriages (1994)
Khuller, Samir, Mitchell, Stephen G, Vazirani, Vijay V
We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This...
Designing multi-commodity flow trees (1994)
Samir Khuller, Balaji Raghavachari, Neal Young
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands. This paper considers the...
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover (1994)
Samir Khuller, Uzi Vishkin, Neal Young
We give an efficient deterministic parallel approximation algorithm for the minimumweight vertex- and set-cover problems and their duals (edge/element packing). The algorithm is simple and suitable...
Biconnectivity Approximations and Graph Carvings (1994)
A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality (1993)
Aggarwal, Alok, Bar-Noy, Amotz, Khuller, Samir, Kravets, Dina, Schieber, Baruch
We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n,...
Maintaining Directed Reachability with Few Edges (1993)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The MEG (minimum equivalent graph) problem is the following: ``Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.'' This problem is...
Maintaining Directed Reachability with Few Edges (1993)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The MEG (minimum equivalent graph) problem is the following: ``Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes.'' This problem is...
Design and Analysis of Algorithms: Course Notes (1993)
These are my lecture notes from CMSC 651: Design and Analysis of Algorithms}, a one semester course that I taught at University of Maryland in the Spring of 1993. The course covers core material in...
Design and Analysis of Algorithms: Course Notes (1993)
These are my lecture notes from CMSC 651: Design and Analysis of Algorithms}, a one semester course that I taught at University of Maryland in the Spring of 1993. The course covers core material in...
Designing Multi-Commodity Flow Trees (1993)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands.This paper considers the...
Designing Multi-Commodity Flow Trees (1993)
Khuller, Samir, Raghavachari, Balaji, Young, Neal
The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands.This paper considers the...
Planar graph coloring is not self-reducible, assuming P ≠ NP (1991)
Vazirani, Vijay V, Khuller, Samir
We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of...
Efficient Parallel Algorithms for Disjoint Paths and Connectivity (1990)
This thesis is concerned with the problem of designing efficient parallel algorithms for various graph-theoretic problems. Our larger goal is to identify "tools" that would be useful in designing...
On-line Algorithms for Weighted Matching and Stable Marriages (1990)
Khuller, Samir, Mitchell, Stephen G., Vazirani, Vijay V.
We give an on-line deterministic algorithm for the bipartite weighted matching problem that achieves a competitive ratio of $O(n)$. In fact, this algorithm is almost optimal - the lower bound on the...
Efficient Parallel Algorithms for Disjoint Paths and Connectivity (1990)
This thesis is concerned with the problem of designing efficient parallel algorithms for various graph-theoretic problems. Our larger goal is to identify "tools" that would be useful in designing...
On-line Algorithms for Weighted Matching and Stable Marriages (1990)
Khuller, Samir, Mitchell, Stephen G., Vazirani, Vijay V.
We give an on-line deterministic algorithm for the bipartite weighted matching problem that achieves a competitive ratio of $O(n)$. In fact, this algorithm is almost optimal - the lower bound on the...
Optimal Enclosure Problems (1990)
Arkin, Esther, Khuller, Samir, Mitchell, Joseph S.B.
We consider the following "fence enclosure" problem: Given a set $S$ of $n$ points in the plane with values $v_{i} \geq 0$, we wish to enclose a subset of the points with a fence (a simple closed...
Optimal Enclosure Problems (1990)
Arkin, Esther, Khuller, Samir, Mitchell, Joseph S.B.
We consider the following "fence enclosure" problem: Given a set $S$ of $n$ points in the plane with values $v_{i} \geq 0$, we wish to enclose a subset of the points with a fence (a simple closed...
Flow in Planar Graphs with Vertex Capacities (1990)
Max-flow in planar graphs has always been studies with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as...
Flow in Planar Graphs with Vertex Capacities (1990)
Max-flow in planar graphs has always been studies with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as...
Efficient parallel algorithms for disjoint paths and connectivity /--Samir Khuller. (1990)
"July 1990."
Planar Graph Coloring is Not Self-Reducible Assuming $P \neq NP$ (1989)
Khuller, Samir, Vazirani, Vijay V.
No abstract is available.
Planar Graph Coloring is Not Self-Reducible Assuming $P \neq NP$ (1989)
Khuller, Samir, Vazirani, Vijay V.
No abstract is available.
Khuller, Samir, Mitchell, Stephen G., Vazirani, Vijay V.
We give an $NC$ algorithm for finding vertex disjoint $s_{1}, t_{1}$ and $s_{2}, t_{2}$ paths in an undirected graph $G$. An important step in solving the general problem is solving the planar case....
Khuller, Samir, Mitchell, Stephen G., Vazirani, Vijay V.
We give an $NC$ algorithm for finding vertex disjoint $s_{1}, t_{1}$ and $s_{2}, t_{2}$ paths in an undirected graph $G$. An important step in solving the general problem is solving the planar case....
Parallel Algorithms for the Subgraph Homeomorphism Problem (1989)
The subgraph homeomorphism problem for a fixed graph $H$ is stated as follows: given a graph $G$, determine whether $G$ has a subgraph homeomorphic to $H$, and obtain it. We study the parallel...
Parallel Algorithms for the Subgraph Homeomorphism Problem (1989)
The subgraph homeomorphism problem for a fixed graph $H$ is stated as follows: given a graph $G$, determine whether $G$ has a subgraph homeomorphic to $H$, and obtain it. We study the parallel...
On Computing Graph Closures (1988)
Given a graph $G$, the closure of $G$ is the graph obtained from $G$ by recursively joining pairs of non-adjacent vertices whose degree sum is at least $n$ until no such pair remains. We give an...
On Computing Graph Closures (1988)
Given a graph $G$, the closure of $G$ is the graph obtained from $G$ by recursively joining pairs of non-adjacent vertices whose degree sum is at least $n$ until no such pair remains. We give an...
Parallel Algorithms for $K_{5}$-minor Free Graphs (1988)
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several...
Parallel Algorithms for $K_{5}$-minor Free Graphs (1988)
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several...
Extending Planar Graph Algorithms to $K_{3}$,$_{3}$-free Graphs (1988)
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several...
Extending Planar Graph Algorithms to $K_{3}$,$_{3}$-free Graphs (1988)
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several...
Equivalence of two linear programming relaxations for broadcast scheduling (0000)
A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the...
Equivalence of two linear programming relaxations for broadcast scheduling
A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the...
Facility Location with Dynamic Distance Functions
Randeep Bhatia, Sudipto Guha, Samir Khuller, Y. J. Sussmann, Ding-zhu Du
. Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a...
Facility Location with Dynamic Distance Functions
Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann
Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a...