NSF Award CCR 9820965:Designing Algorithms for NP-hard Graph Problems
Abstract: Graphs are powerful tools that can be used to model objects and relationships between objects. Indeed, many distinct problems can be cast as optimization problems in graph theoretic terms. Essentially, graph theory provides an excellent way to model problems related to transportation, network design, scheduling, robotics and many other areas. This permits us to develop and illustrate the power of different algorithmic tools. I am interested in optimization problems that arise in a variety of contexts. Many of these problems are computationally intractable and thus we are looking for algorithms that produce close to optimal solutions, in polynomial time.
S. Khuller and A. Zhu. The General Steiner Tree-Star Problem. Information Processing Letters (2002) .
Sudipto Guha, Rafi Hassin, Samir Khuller and Einat Or. Capacitated vertex covering with applications . SODA 2002. Accepted to J. of Algorithms .
Rajiv Gandhi, Samir Khuller and Aravind Srinivasan. Approximation Algorithms for Partial Covering Problems. ICALP 2001. To appear J. of Algorithms .
Suman Banerjee and Samir Khuller. A Clustering Scheme for Hierarchical Routing in Wireless Networks. INFOCOM 2001.
Moses Charikar, Samir Khuller, Giri Narasimhan and Dave Mount. Facility Location with Outliers. 12th Symposium on Discrete Algorithms (SODA), (Jan 2001), Washington DC.
Samir Khuller, Randeep Bhatia and Robert Pless. On Local Search and Placement of Meters in Networks. 11th Symposium on Discrete Algorithms (SODA), (Jan 2000), San Francisco. SIAM Journal on Computing (2003).
Randeep Bhatia, Samir Khuller, Robert Pless and Yoram J. Sussmann. The Full Degree Spanning Tree Problem. 10th Symposium on Discrete Algorithms (SODA), (Jan '99), Baltimore. (short paper). Networks Vol 36(4), pp. 1--7, (2000) .
Samir Khuller, Azriel Rosenfeld and Angela Wu. Centers of sets of pixels. Discrete Applied Mathematics Vol 103, pp. 297--306, (2000).
Sudipto Guha and Samir Khuller. Greedy Strikes Back: Improved Algorithms for Facility Location. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (Jan '98), San Francisco, CA. Journal of Algorithms Vol 31(1) (1999), pp. 228-248.
Randeep Bhatia, Sudipto Guha, Samir Khuller and Yoram J. Sussmann. Facility Location with Dynamic Distance Functions. 6th Scandinavian Workshop on Algorithm Theory (SWAT), (Jul '98), Stockholm, Sweden. Invited to Journal of Combinatorial Optimization Vol 2 (1998) pp. 199--217.
Sudipto Guha and Samir Khuller. Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. 1998 FST&TCS Conference (Madras, India). Information and Computation Vol 150, pp. 57--74 (1999).
Samir Khuller, Robert Pless and Yoram J. Sussmann. Fault Tolerant K-Center Problems. 3rd Italian Conference on Algorithms and Complexity (CIAC), (Mar '97), Rome, Italy. Theoretical Computer Science Vol 242 (1-2), pp. 237-245, (2000).
Samir Khuller, Anna Moss and Joseph Naor. The Budgeted Maximum Coverage Problem. Information Processing Letters Vol. 70(1), pp. 39--45, (1999) .
Samir Khuller and Yoram J. Sussmann. The Capacitated K-Center Problem. 4th Annual European Symposium on Algorithms (ESA), (Sep '96), Barcelona, Spain. SIAM Journal on Discrete Mathematics Vol 13(3), pp. 403--418, (2000).
Sudipto Guha and Samir Khuller. Approximation Algorithms for Connected Dominating Sets. 4th Annual European Symposium on Algorithms (ESA), (Sep '96), Barcelona, Spain. Algorithmica Vol 20 (1998), pp. 374--387.
Leonid Zosin and Samir Khuller. On directed Steiner trees. SODA 2002.
Samir Khuller and Balaji Raghavachari. Improved Approximation Algorithms for Uniform Connectivity Problems. 27th Symposium on Theory of Computing (STOC), (May '95), Las Vegas. Journal of Algorithms Vol 21(2) (1996) pp. 434--450.
Samir Khuller, Balaji Raghavachari and An Zhu. A Uniform Framework for Approximating Weighted Connectivity Problems. 10th Symposium on Discrete Algorithms (SODA), (Jan '99), Baltimore. (short paper).
Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari and Neal Young. A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees. 5th Integer Programming and Combinatorial Optimization Conference (IPCO), (June '96), Vancouver, Canada. Journal of Algorithms Vol 24(2) (1997) pp 310--324.
S. Khuller, Y. Kim and Y-C. Wan. On generalized broadcasting and gossiping. ESA 2003.
S. Kashyap and S. Khuller. Algorithms for Non-Uniform Size Data Placement on Parallel Disks. FSTTCS 2003.
S. Bhattacharjee, W. C. Cheng, C.-F. Chou, L. Golubchik, S. Khuller. Bistro: a Platform for Building Scalable Wide-Area Upload Applications. ACM SIGMETRICS Performance Evaluation Review (also presented at the Workshop on Performance and Architecture of Web Servers (PAWS) in June 2000). Volume 28, Number 2, September 2000, pp. 29-35.
B. Cheng, C.F Chou, L. Golubchik, S. Khuller. A Secure and Scalable Web Upload Service Architecture. International Conference on Internet Computing (IC 2001), (Jun '01),
C.F Chou, Y-C. Wan, B. Cheng, L. Golubchik, S. Khuller. A performance study of a large scale data collection problem, . 7th International Workshop on Web Content Caching and Distribution, (IWCW 2002), (Aug '02),
B. Cheng, C.F. Chou, L. Golubchik, S. Khuller, Y-C. Wan. Large scale data collection: a co-ordinated approach. . INFOCOM 2003
Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramki Thurimella and An Zhu. Approximation Algorithms for Data Placement on Parallel Disks. 11th Symposium on Discrete Algorithms (SODA), (Jan 2000), San Francisco.
R. Gandhi, S. Khuller, S. Parthasarathy and A. Srinivasan. Dependent Rounding on Bipartite Graphs. 43rd Conference Foundations of Computer Science (FOCS), (Nov '02).
Randeep Bhatia, Samir Khuller and Joseph (Seffi) Naor. The Loading Time Scheduling Problem. 36th Conference on Foundations of Computer Science (FOCS), (Oct '95), Milwaukee. Journal of Algorithms Vol 36(1), pp. 1--33 (2000).
Moses Charikar, Samir Khuller and Balaji Raghavachari. Algorithms for Capacitated Vehicle Routing. 30th Symposium on Theory of Computing (STOC), (May '98), Dallas. SIAM Journal on Computing Vol 31(3), pp. 665--682 (2001).
Nili Guttmann-Beck, Rafi Hassin, Samir Khuller and Balaji Raghavachari. Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem. 1998 FST&TCS Conference (Madras, India). Algorithmica Vol 28 pp. 422--437, (2000).
Samir Khuller. An O(V^2) algorithm for Single Connectedness. Information Processing Letters Vol 72(3-4), pp. 105--107, (1999) .
Ruth Ben-Yashar, Samir Khuller, Sarit Kraus. Optimal collective dichotomous choice under partial order constraints. Mathematical Social Sciences Vol 41, pp. 349--364, (2001).
Rafi Hassin, Samir Khuller. Z-Approximations. Journal of Algorithms Vol 41(2), pp. 429--442 (2001).