Listed in order by year when first presented at a conference.

2018

S. Khuller, J. Li, P. Sturmfels, K. Sun and P. Venkat. Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time. LATIN 2018. Submitted to Theoretical Computer Science.

S. Kumar, S. Khuller. Brief Announcement: A Greedy 2 approximation algorithm for the active time problem. SPAA 2018.

I. Bercea, S. Khuller, A. Kumar. k-Center with fairness constraints. (in preparation).

S. Grover, N. Gupta, S. Khuller A. Pancholi. Constant factor approximation algorithm for uniform hard capacitated knapsack median problem. FST&TCS 2018 (submitted).

2017

S. Khuller, F. Koehler. BusyTime Scheduling: Online and Offline Algorithms. 2017 WADS.

S. Ahmadi, S. Khuller, M. Purohit and S. Yang. On Scheduling Co-Flows. To appear in Integer Programming and Combinatorial Optimization (IPCO), 2017. Full version under review for Algorithmica.

2016

S. Khuller, M. Purohit. Brief Announcement: Improved approximation algorithms for scheduling co-flows. SPAA 2016.

R. Murray, M. Chao and S. Khuller. Scheduling distributed clusters of parallel machines: primal dual and LP based approximation algorithms. ESA 2016. Full version Algorithmica.

I. Bercea, V. Isler, S. Khuller. Minimizing Uncertainty through Sensor Placement with Angle Constraints. CCCG 2016.

S. Khuller, S. Yang. Revisiting Connected Dominating Sets: An optimal local algorithm? APPROX 2016. Full version under review for Algorithmica.

2015

H. Daume, S. Khuller, M. Purohit, G. Sanders. On correcting inputs: Inverse optimization with a margin. FST&TCS 2015.

2014

S. Khuller, M. Purohit, K. K. Sarpatwar. Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems. 2014 SODA.

J. Chang, S. Khuller, K. Mukherjee. LP Rounding and Combinatorial Algorithms for minimizing active and busy time. 2014 SPAA. Full version to appear in Special Issue of Journal of Scheduling.

S. Arora, N. Gupta, S. Khuller, Y. Sabharwal and S. Singhal. Facility Location with red-blue demands. Operations Research Letters 42 (6-7): 462-465 (2014).

2013

F. Koehler and S. Khuller. Optimal batch schedules for parallel machines. 2013 WADS.

K. Mukherjee, S. Khuller, A. Deshpande. Algorithms for the Thermal Scheduling Problem. 2013 IPDPS.

L. Golubchik, S. Khuller, K. Mukherjee and Y. Yao. To send or not to send: Reducing the cost of data transmission. 2013 INFOCOM.

J. Chang and S. Khuller. A Min-Edge Cost Flow Framework for Capacitated Covering Problems. ALENEX 2013.

A. K. Kayyoor, A. Deshpande and S. Khuller. Data Placement and Replica Selection for Improving Co-location in Distributed Environments.

2012

K. Mukherjee, S. Khuller, A. Deshpande. Saving on Cooling: The Thermal Scheduling Problem. SIGMETRICS 2012 (poster).

B.Saha and S. Khuller. Set Cover revisited: Hypergraph Cover with Hard Capacities. ICALP 2012. A more complete version.

J. Chang, H. Gabow and S. Khuller. A model for minimizing active processor time. ESA 2012. Full version to appear in special issue of Algorithmica

S. Khuller, B. Saha and K. K. Sarpatwar. New Approximation Results for Resource Replication Problems. APPROX 2012. Full version in Algorithmica.

G. Duggal, R. Patro, E. Sefer, H. Wang, D. Filippova, S. Khuller and C. Kingsford. Resolving Spatial Inconsistencies in Chromosome Conformation Data. WABI 2012. Invited to special issue of BMC from WABI.

M. Cygan, M.T. Hajiaghayi and S. Khuller. LP Rounding for $k$-Centers with Non-uniform Hard Capacities. FOCS 2012.

2011

A. Thor, P. Anderson, L. Raschid, S. Navlakha, B. Saha, S. Khuller, X. Zhang. Link Prediction for Annotation Graph Datasets using Graph Summarization. 2011 Int. Semantic Web Conference, Bonn.

J. Li and S. Khuller. Generalized Machine Activation Problems. SODA 2011.

2010

C. Chekuri, A. Gal, S. Im, S. Khuller, J. Li, R. McCutchen, B. Moseley and L. Raschid. New Models and Algorithms for Throughput Maximization in Broadcast Scheduling WAOA 2010.

E. Bortnikov, S. Khuller, J.Li, Y. Mansour and S. Naor. The Load-Distance Balancing Problem. To appear Special Issue of Networks from INOC 2009.

S. Khuller, J. Li and B. Saha. Energy efficient scheduling via partial shutdown. SODA 2010.

S. Khuller and J. Chang. How many places to apply to and how many to accept? Submitted for publication. See article by Daneil de Vise .

J. Li, A. Deshpande and S. Khuller. On Computing Compression Trees for Data Collection in Wireless Sensor Networks. INFOCOM 2010 .

A. Deshpande, S. Khuller and A. Srivastava. A case for spatially-aware optmization in data centers Submitted.

B. Saha, A. Hoch, S. Khuller, L. Raschid and X. Zhang. Dense Subgraphs with Restrictions and Applications to Gene Annotation Graphs. RECOMB 2010.

2009

S. Khuller and B. Saha. On finding dense subgraphs. ICALP 2009. Journal submission.

S. Alaei, E. Arcaute, S. Khuller, W. Ma, A. Malekian and J. Tomlin Online Allocation of Display Advertisements Subject to Advanced Sales Contracts}. 2009 Workshop on Data Mining and Audience Intelligence for Advertising.

E. Bortnikov, S. Khuller, Y. Mansour and S. Naor. The Load-Distance Balancing Problem. 2009 International Network Optimization Conference (INOC) .

J. Li, A. Deshpande and S. Khuller. Minimizing communication cost in distributed multi-query processing. 2009 International Conference on Data Engineering (ICDE) (Shanghai).

A. Chow, L. Golubchik, S. Khuller and Y. Yao. On the tradeoff between playback delay and buffer space in streaming. 2009 IPDPS (Rome, Italy).

S. Khuller and R. McCutchen. Assigning reviewers to papers. Under preparation.

2008

S. Khuller and J. Mestre. An Optimal Incremental Algorithm for Minimizing Lateness with Rejection 2008 European Symposium on Algorithms (ESA). Submitted for publication Journal.

R. McCutchen and S. Khuller. Streaming algorithms for $k$-center clustering with outliers and with anonymity 2008 Workshop on Approximation Algorithms (APPROX).

J. Chang, T. Erlebach, R. Gailis and S. Khuller. Broadcast Scheduling: Algorithms and Complexity. 2008 Symp. on Discrete Algorithms (SODA) . To appear in ACM Trans. on Algorithms.

A. Deshpande, S. Khuller, A. Malekian and M. Toossi. Energy Efficient Monitoring in Sensor Networks. LATIN 2008. Invited to special issue of Algorithmica.

2007

S. Khuller, A. Malekian and J. Mestre. The Gas Station Problem. 2007 European Symp. on Algorithms (ESA). To appear in ACM Trans. on Algorithms.

S. Khuller, M. Martinez, D. Nau, G. Simari, A. Sliva, V.S. Subrahmanian. Finding most probable worlds of probabilistic logic programs. SUM 2007 . Full version in Ann. Math. Artificial Intelligence (2007).

2006

S. Kashyap, S. Khuller, Y-C. Wan and L. Golubchik. Fast Reconfiguration of Data Placement in Parallel Disks. 2006 ALENEX.

M. Charikar and S. Khuller. A robust maximum completion time measure for scheduling. 2006 Symp. on Discrete Algorithms (SODA).

J. Bleiholder, S. Khuller, F. Naumann, L. Raschid and Y. Wu. Query Planning in the presence of overlapping sources. EDBT (2006).

A. Kashyap, S. Khuller and M. Shayman. Relay placement for higher order connectivity in sensor networks. INFOCOM (2006). Submitted for journal publication.

G. Aggarwal, T. Feder, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas and A. Zhu. Achieving anonymity via clustering. 2006 Principles of Database Systems (PODS). Full version Accepted to ACM Trans. on Algorithms.

S. Khuller, Y-A. Kim, A.Malekian. Improved algorithms for Data migration. 2006 Workshop on Approximation Algorithms (APPROX). Full version accepted to Algorithmica.

2005

S. Khuller, B. Raghavachari and N. Young. Greedy Methods. Book Chapter.

S. Khuller, K. Lee and M. Shayman. On Degree Constrained Shortest Paths. 2005 European Symp. on Algorithms (ESA).

S. Khuller, Y. Kim and Y-C. Wan. Broadcasting on Networks of Workstations. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005). Full version in Algorithmica (2008).

2004

L. Golubchik, S. Khuller, Y. Kim, S. Shargorodksaya and Y-C. Wan. Data migration on parallel disks. 2004 European Symp. on Algorithms (ESA). Full version in special Issue of Algorithmica from ESA 2004.

S. Khuller, Y. Kim and G. Woeginger. A polynomial time approximation scheme for broadcasting in heterogenous networks. APPROX 2004. Full version in Algorithmica, Vol 48(1):1--21 (2007)(merged with SODA 2004 paper).

S. Khuller and Y. Kim. On broadcasting in heterogenous networks. 2004 Symp. on Discrete Algorithms (SODA). Full version in Algorithmica, Vol 48(1):1--21 (2007).

2003

R. Gailis and S. Khuller. Broadcast Scheduling with Deadlines. Manuscript .

S. Khuller and Y. Kim. Equivalence of Two Linear Programming Relaxations for Broadcast Scheduling. Operations Research Letters Vol 32(5):473--478 (2004)

S. Khuller, Y. Kim and Y-C. Wan. On generalized broadcasting and gossiping. 2003 European Symp. on Algorithms (ESA). Full version in Journal of Algorithms (2005) .

S. Kashyap and S. Khuller. Algorithms for Non-Uniform Size Data Placement on Parallel Disks. FST&TCS 2003. Full version in Journal of Algorithms (2005) .

R. Gandhi, S. Khuller, A. Srinivasan and N. Wang. Approximation algorithms for channel allocation problems in broadcast networks . APPROX 2003. Full version in Networks (2006).

R.Gandhi, E. Halperin, S. Khuller, G. Kortsarz and A.Srinivasan. An improved approximation algorithm for vertex cover with hard capacities. ICALP 2003 . Full version in JCSS Vol 72(1):16--33 (2006).

B. Cheng, C.F. Chou, L. Golubchik, S. Khuller, Y-C. Wan. Large scale data collection: a co-ordinated approach. . INFOCOM 2003. IEEE Journal on Special Areas in Communication (Special Issue on Design, Implementation and Analysis of Communication Protocols). Vol 22(1): 2004--2019, (2004).

S. Banerjee, C. Kommareddy, K. Kar, B. Bhattacharjee and S. Khuller. Construction of an Efficient Overlay Multicast Infrastructure for Real-Time Applications. INFOCOM 2003

S. Khuller, Y. Kim and Y-C. Wan. Algorithms for Data Migration with Cloning. 22nd ACM Principles of Database Conference (PODS) 2003. Full version in SIAM J. on Computing Vol 33(2): 448--461, (2004).

2002

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),

R. Gandhi, S. Khuller, Y. Kim and Y-C. Wan. Approximation algorithms for broadcast scheduling. 9th Conference on Integer Programming and Combinatorial Optimization (IPCO) 2002. Full version in Algorithmica Vol 38: 597--608, (2004).

R. Gandhi, S. Khuller, S. Parthasarathy and A. Srinivasan. Dependent Rounding on Bipartite Graphs. 43rd Conference Foundations of Computer Science (FOCS), (Nov '02). Full version in JACM.

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. J. of Algorithms Vol 48(1), pp. 257--270, (2003).

Leonid Zosin and Samir Khuller. On directed Steiner trees. SODA 2002.

2001

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).

Rajiv Gandhi, Samir Khuller and Aravind Srinivasan. Approximation Algorithms for Partial Covering Problems. ICALP 2001. J. of Algorithms Vol 53(1): 55--84 (2004).

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.

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),

2000

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. Full version To appear ACM Trans. on Algorithms.

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 Vol 32(2), pp. 470--487, (2003).

Samir Khuller, Azriel Rosenfeld and Angela Wu. Centers of sets of pixels. Discrete Applied Mathematics Vol 103, pp. 297--306, (2000).

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.

1999

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). Full version . Networks Vol 36(4), pp. 1--7, (2000) .

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).

Samir Khuller. An O(V^2) algorithm for Single Connectedness. Information Processing Letters Vol 72(3-4), pp. 105--107, (1999) .

Samir Khuller, Anna Moss and Joseph Naor. The Budgeted Maximum Coverage Problem. Information Processing Letters Vol. 70(1), pp. 39--45, (1999) .

1998

Samir Khuller. A linear time algorithm for Lewis-Carrol's voting system. Unpublished (1998).

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).

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).

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).

1997

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).

1996

S. Khuller, B. Raghavachari and A. Rosenfeld. Landmarks in Graphs Discrete Applied Mathematics, Vol. 70 (3), pp. 217-229 (1996).

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.

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, B. Raghavachari and N. Young. On Strongly Connected Digraphs with Bounded Cycle Length. Discrete Applied Mathematics, Vol 69 (3) (1996) pp. 281--289.

1995

A. Bar-Noy, S. Khuller and B. Schieber. The complexity of finding most vital arcs and nodes. CS-TR-3539. Technical Report, University of Maryland (1995).

S. Khuller and Y. Matias. A Simple Randomized Sieve Algorithm for the Closest-Pair Problem Information and Computation, Vol 188 (1), pp. 34--37, (1995).

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.

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).

S. Khuller, A. Rosenfeld and E. Rivlin. Graphbots: Mobility in Discrete Spaces . 22nd International Colloquium on Automata, Languages and Programming Conference (ICALP), (July '95), Szeged, Hungary. IEEE Transactions on Systems, Man and Cybernetics Vol 28(1) (1998) pp 29-38.

1994

S. Khuller and U. Vishkin. On the Parallel Complexity of Digraph Reachability. Information Processing Letters Vol 52 (5), pp. 239--241, (1994) .

Samir Khuller, Balaji Raghavachari and Neal Young. Approximating the Minimum Equivalent Digraph . ACM-SIAM Symp. on Discrete Algorithms (SODA) (Jan '94). SIAM Journal on Computing, Vol 24 (4) pp. 859--872, (1995).

Samir Khuller, Balaji Raghavachari and Neal Young. Low Degree Spanning Trees of Small Weight . 26th Symposium on Theory of Computing (STOC), (May '94), Montreal. SIAM Journal on Computing Vol 25 (2) pp. 355--368, (1996).

1993

S. Khuller, J. Naor and P. Klein. The Lattice Structure of Flow in Planar Graphs. SIAM Journal of Discrete Mathematics, Vol 6 (3) pp. 477--490, (1993).

S. Khuller, B. Raghavachari and N. Young. Designing Multi-Commodity Flow Trees . Workshop on Algorithms and Data Structures (WADS), (Aug '93), Montreal, Canada. Information Processing Letters, Vol 50(1) (1994) pp. 49--55.

S. Khuller, B. Raghavachari and N. Young, Balancing Minimum Spanning and Shortest Path Trees. 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (Jan '93), Austin. Algorithmica, Vol 14(4) (1995) pp. 305--321.

S. Khuller, U. Vishkin and N. Young. A Primal Dual Parallel Approximation Technique Applied to Weighted Set and Vertex Cover. 1993 IPCO Conference (Erice, Italy). Full version in Journal of Algorithms, Vol 17(2): 280--289, (1994).

1992

S. Khuller and B. Schieber. On Independent Spanning Trees. Information Processing Letters, Vol 42(6):321--323 (1992).

S. Khuller and U. Vishkin. Biconnectivity Approximations and Graph Carvings. 1992 STOC (Victoria). Full version in Journal of the ACM , Vol 41(2):214--235 (1994).

S. Khuller and R. Thurimella. Approximation Algorithms for Graph Augmentation. 1992 ICALP (Wien). Full version in Journal of Algorithms, Vol 14(2):214--225 (1993).

A. Aggarwal, A. Bar-Noy, S. Khuller, D. Kravets and B. Schieber. Efficient Minimum Cost Matching Using Quadrangle Inequality . 1992 FOCS (Pittsburgh). Full version in Journal of Algorithms, Vol 19(1): 116--143 (1995).

1991

E. Arkin, S. Khuller and J. Mitchell. Geometric Knapsack Problems. 1991 WADS Conference, Ottawa. Full version in Algorithmica, Vol 10: 399--427 (1993).

S. Khuller, S. Mitchell and V. Vazirani. Online algorithms for weighted matchings and stable marriages . 1991 ICALP (Madrid). Full version in Theoretical Computer Science, Vol 127 (2): 255--267 (1994).

S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest pair problem . 1991 CCCG Conference (Vancouver). Full version in Information and Computation, Vol 188(1):34--37 (1995).

S. Khuller and V. Vazirani. Planar Graph Coloring is not Self-Reducible, assuming P # NP. Theoretical Computer Science, VOl 88(1): 183--190 (1991).

1990

S. Khuller and J. Naor. Flow in Planar Graphs with Vertex Capacities. 1990 IPCO Conference (Waterloo). Full version in Algorithmica (Special Issue on Network Flows), Vol 11:200-225 (1994).

S. Khuller. Coloring algorithms for K5-minor free graphs. Information Processing Letters, Vol 33 (4):203--208, (1990).

S. Khuller and J. Mitchell. On a triangle counting problem. Information Processing Letters, Vol 33 (6):319--322, (1990).

1989

S. Khuller. Parallel Algorithms for the Subgraph Homeomorphism problem. 1989 WADS Conference, Ottawa, Canada.

S. Khuller, S. Mitchell and V. Vazirani. Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph. 1989 FOCS (Raleigh). Full version in SIAM J. on Computing, Vol 21(3):486--506 (1992).

S. Khuller and B. Scheiber. Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs. 1989 FOCS (Raleigh). Full version in SIAM J. on Computing, Vol 20(2):352--375 (1991).

S. Khuller. On Computing Graph Closures. Information Processing Letters, Vol 31 (5):249--255 (1989).

1988

S. Khuller. Extending Planar Graph Algorithms to K_3,3 Graphs. FSTTCS 1988, India. Full version in Information and Computation, Vol 80(1):13--25 (1990).