@String{approx = " APPROX"}
@String{dcg =    "Discrete Comput. Geom."}
@String{esa =   " ESA"}
@String{focs =   " FOCS"}
@String{icalp =  " ICALP"}
@String{infocom = " INFOCOM"}
@String{ipco =   " IPCO"}
@String{ipl =    "Info. Proc. Letters"}
@String{jalg =   "J.\ Algorithms"}
@String{jcss =   "JCSS"}
@String{jcta =   "J.\ Combinatorial Theory A"}
@String{jctb =   "J.\ Combinatorial Theory B"}
@String{latin =   " LATIN"}
@String{lncs =   "LNCS"}
@String{proc =   ""}
@String{podc = " PODC"}
@String{sicomp = "SICOMP"}
@String{sidm =   "SIAM J.\ Disc.\ Math."}
@String{soda =   " SODA"}
@String{socg =    " SOCG"}
@String{fsttcs =    " FST\&TCS"}
@String{stacs =    " STACS"}
@String{spaa =    " SPAA"}
@String{stoc =   " STOC"}
@String{ta =     "To appear"}
% This file was created with JabRef 2.9.2.
% Encoding: Cp1252

@INPROCEEDINGS{ABCDGKNS05,
  author = {Ittai Abraham and Yair Bartal and T.-H. Hubert Chan and Kedar Dhamdhere
	and Anupam Gupta and Jon M. Kleinberg and Ofer Neiman and Aleksandrs
	Slivkins},
  title = {Metric Embeddings with Relaxed Guarantees},
  booktitle = focs,
  year = {2005},
  pages = {83-100},
  doi = {http://dx.doi.org/10.1109/SFCS.2005.51}
}

@INPROCEEDINGS{AndoniDGIR03,
  author = {Alexandr Andoni and Michel Marie Deza and Anupam Gupta and Piotr
	Indyk and Sofya Raskhodnikova},
  title = {Lower Bounds for Embedding Edit Distance into Normed Spaces},
  booktitle = soda,
  year = {2003},
  pages = {523--526},
  doi = {http://doi.acm.org/10.1145/644108.644196}
}

@ARTICLE{AGGN10,
  author = {Barbara M. Anthony and Vineet Goyal and Anupam Gupta and Viswanath
	Nagarajan},
  title = {A Plant Location Guide for the Unsure: Approximation Algorithms for
	Min-Max Location Problems},
  journal = {Math. Oper. Res.},
  year = {2010},
  volume = {35},
  pages = {79-101},
  number = {1},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1287/moor.1090.0428},
  eprint = {http://mor.journal.informs.org/cgi/reprint/35/1/79.pdf},
  url = {http://mor.journal.informs.org/cgi/content/abstract/35/1/79}
}

@INPROCEEDINGS{AGGN08-proc,
  author = {Barbara M. Anthony and Vineet Goyal and Anupam Gupta and Viswanath
	Nagarajan},
  title = {A plant location guide for the unsure},
  booktitle = soda,
  year = {2008},
  pages = {1164--1173},
  doi = {http://doi.acm.org/10.1145/1347082.1347209}
}

@INPROCEEDINGS{AG07,
  author = {Barbara M. Anthony and Anupam Gupta},
  title = {Infrastructure Leasing Problems},
  booktitle = ipco,
  year = {2007},
  pages = {424--438},
  doi = {http://dx.doi.org/10.1007/978-3-540-72792-7_32}
}

@INPROCEEDINGS{BDGRRRS05,
  author = {Mihai B\u{a}doiu and Kedar Dhamdhere and Anupam Gupta and Yuri Rabinovich
	and Harald R{\"a}cke and R. Ravi and Anastasios Sidiropoulos},
  title = {Approximation Algorithms for Embeddings Into Low-Dimensional Spaces},
  booktitle = soda,
  year = {2005},
  pages = {119--128},
  doi = {http://doi.acm.org/10.1145/1070432.1070449}
}

@INPROCEEDINGS{bdgit-soda09,
  author = {Babaioff, Moshe and Dinitz, Michael and Gupta, Anupam and Immorlica,
	Nicole and Talwar, Kunal},
  title = {Secretary problems: weights and discounts},
  booktitle = soda,
  year = {2009},
  pages = {1245--1254},
  doi = {http://doi.acm.org/10.1145/1496770.1496905}
}

@INPROCEEDINGS{BGGN13,
  author = {Maxim Babenko and Andrew V. Goldberg and Anupam Gupta and Viswanath
	Nagarajan},
  title = {Algorithms for Hub Label Optimization},
  booktitle = icalp,
  year = {2013},
  month = {Jul},
}

@ARTICLE{BBG09-jacm,
  author = {Maria-Florina Balcan and Avrim Blum and Anupam Gupta},
  title = {Approximate clustering without the approximation},
  journal = {JACM},
  year = {to appear},
}

@INPROCEEDINGS{BBG09,
  author = {Maria-Florina Balcan and Avrim Blum and Anupam Gupta},
  title = {Approximate clustering without the approximation},
  booktitle = soda,
  year = {2009},
  pages = {1068-1077},
  doi = {http://doi.acm.org/10.1145/1496770.1496886}
}

@ARTICLE{BBGN12,
  author = {Nikhil Bansal and Niv Buchbinder and Anupam Gupta and Joseph Naor},
  title = {A Randomized {$O(\log^2 k)$}-Competitive Algorithm for Metric Bipartite
	Matching},
  journal = {Algorithmica},
  year = {2012},
  pages = {1-14},
  doi = {http://dx.doi.org/10.1007/s00453-012-9676-9}
}

@INPROCEEDINGS{BBGN07-esa,
  author = {Nikhil Bansal and Niv Buchbinder and Anupam Gupta and Joseph Naor},
  title = {An {$O(\log^2 k)$}-Competitive Algorithm for Metric Bipartite Matching},
  booktitle = esa,
  year = {2007},
  pages = {522-533},
  doi = {http://dx.doi.org/10.1007/978-3-540-75520-3_47}
}

@INPROCEEDINGS{bgk-soda10,
  author = {Nikhil Bansal and Anupam Gupta and Ravishankar Krishnaswamy},
  title = {A Constant Factor Approximation Algorithm for Generalized Min-Sum
	Set Cover},
  booktitle = {SODA},
  year = {2010},
  pages = {1539-1545},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1873601.1873726},
  ee = {http://www.siam.org/proceedings/soda/2010/SODA10_125_bansaln.pdf}
}

@INPROCEEDINGS{BansalGKNPS12,
  author = {Nikhil Bansal and Anupam Gupta and Ravishankar Krishnaswamy and Viswanath
	Nagarajan and Kirk Pruhs and Cliff Stein},
  title = {Multicast Routing for Energy Minimization Using Speed Scaling},
  booktitle = {First Mediterranean Conference on Algorithms (MedAlg)},
  year = {2012},
  pages = {37-51},
  month = {Dec},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-34862-4_3}
}

@ARTICLE{BGLMNR12,
  author = {Nikhil Bansal and Anupam Gupta and Jian Li and Juli{\'a}n Mestre
	and Viswanath Nagarajan and Atri Rudra},
  title = {When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic
	Matchings},
  journal = {Algorithmica},
  year = {2012},
  volume = {63},
  pages = {733-762},
  number = {4},
  doi = {http://dx.doi.org/10.1007/s00453-011-9511-8}
}

@INPROCEEDINGS{BGLMNR10,
  author = {Nikhil Bansal and Anupam Gupta and Jian Li and Juli{\'a}n Mestre
	and Viswanath Nagarajan and Atri Rudra},
  title = {When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic
	Matchings},
  booktitle = {ESA (2)},
  year = {2010},
  pages = {218-229},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-15781-3_19}
}

@ARTICLE{BGLMNR10-arxiv,
  author = {Nikhil Bansal and Anupam Gupta and Jian Li and Juli{\'a}n Mestre
	and Viswanath Nagarajan and Atri Rudra},
  title = {When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic
	Matchings},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1008.5356},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1008.5356}
}

@ARTICLE{BGKMPT11-tocs,
  author = {Blelloch, Guy E. and Gupta, Anupam and Koutis, Ioannis and Miller,
	Gary L. and Peng, Richard and Tangwongsan, Kanat},
  title = {Nearly-Linear Work Parallel SDD Solvers, Low-Diameter Decomposition,
	and Low-Stretch Subgraphs},
  journal = {Theory of Computing Systems (Special Issue for SPAA 2011 papers)},
  year = {2013},
  pages = {1-34},
  doi = {http://dx.doi.org/10.1007/s00224-013-9444-5},
  issn = {1432-4350},
  keywords = {Parallel algorithms; Linear systems; Low-stretch spanning trees; Low-stretch
	subgraphs; Low-diameter decomposition},
  publisher = {Springer-Verlag}
}

@INPROCEEDINGS{BlellochGKMPT11,
  author = {Guy E. Blelloch and Anupam Gupta and Ioannis Koutis and Gary L. Miller
	and Richard Peng and Kanat Tangwongsan},
  title = {Near linear-work parallel SDD solvers, low-diameter decomposition,
	and low-stretch subgraphs},
  booktitle = {SPAA},
  year = {2011},
  pages = {13-22},
  month = {May},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1989493.1989496}
}

@INPROCEEDINGS{BGT11,
  author = {Guy E. Blelloch and Anupam Gupta and Kanat Tangwongsan},
  title = {Parallel Probabilistic Tree Embeddings, {k}-Median, and Buy-at-Bulk
	Network Design},
  booktitle = {SPAA},
  year = {2012},
  month = {Aug},
  doi = {http://doi.acm.org/10.1145/2312005.2312045}
}

@ARTICLE{BGMS11-arxiv,
  author = {Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma},
  title = {Welfare and Profit Maximization with Production Costs},
  journal = {CoRR},
  year = {2011},
  volume = {abs/1110.4992},
  ee = {http://arxiv.org/abs/1110.4992},
  url = {http://arxiv.org/abs/1110.4992}
}

@INPROCEEDINGS{BGMS11-focs,
  author = {Avrim Blum and Anupam Gupta and Yishay Mansour and Ankit Sharma},
  title = {Welfare and Profit Maximization with Production Costs},
  booktitle = {FOCS},
  year = {2011},
  pages = {77-86},
  month = {Nov},
  doi = {http://dx.doi.org/10.1109/FOCS.2011.68}
}

@INPROCEEDINGS{BGPS13,
  author = {Avrim Blum and Anupam Gupta and Ariel Procaccia and Ankit Sharma},
  title = {Harnessing the Power of Two Crossmatches},
  booktitle = {14th ACM Conference on Electronic Commerce},
  year = {2013},
  month = {Jul},
}

@INPROCEEDINGS{BGGKR07,
  author = {Yuri Breitbart and Minos N. Garofalakis and Anupam Gupta and Amit
	Kumar and Rajeev Rastogi},
  title = {On Configuring {BGP} Route Reflectors},
  booktitle = {2nd International Conference on COMmunication System softWAre and
	MiddlewaRE (COMSWARE)},
  year = {2007},
  doi = {http://dx.doi.org/10.1109/COMSWA.2007.382444}
}

@ARTICLE{CCGKufp01,
  author = {Amit Chakrabarti and Chandra Chekuri and Anupam Gupta and Amit Kumar},
  title = {Approximation Algorithms for the Unsplittable Flow Problem},
  journal = {Algorithmica},
  year = {2007},
  volume = {47},
  pages = {53--78},
  number = {1},
  doi = {http://dx.doi.org/10.1007/s00453-006-1210-5},
  fjournal = {Algorithmica. An International Journal in Computer Science}
}

@INPROCEEDINGS{CCGKufp01-conf,
  author = {Amit Chakrabarti and Chandra Chekuri and Anupam Gupta and Amit Kumar},
  title = {Approximation Algorithms for Unsplittable Flow Problems},
  booktitle = approx,
  year = {2002},
  volume = {2462},
  series = lncs,
  pages = {51--66},
  doi = {http://dx.doi.org/10.1007/3-540-45753-4_7}
}

@ARTICLE{CDGKS09,
  author = {T.-H. Hubert Chan and Kedar Dhamdhere and Anupam Gupta and Jon M.
	Kleinberg and Aleksandrs Slivkins},
  title = {Metric Embeddings with Relaxed Guarantees},
  journal = {SIAM Journal on Computing},
  year = {2009},
  volume = {38},
  pages = {2303-2329},
  number = {6},
  doi = {http://dx.doi.org/10.1137/060670511},
  keywords = {metric embeddings; low-distortion embeddings; metric spaces; metric
	decompositions; randomized algorithms}
}

@INPROCEEDINGS{ChanDG06,
  author = {T.-H. Hubert Chan and Michael Dinitz and Anupam Gupta},
  title = {Spanners with Slack},
  booktitle = esa,
  year = {2006},
  pages = {196-207},
  doi = {http://dx.doi.org/10.1007/11841036_20}
}

@ARTICLE{CG08-sicomp,
  author = {T.-H. Hubert Chan and Anupam Gupta},
  title = {Approximating TSP on Metrics with Bounded Global Growth},
  journal = {SIAM Journal on Computing},
  year = {2012},
  volume = {41},
  pages = {587-617},
  number = {3},
  doi = {http://dx.doi.org/10.1137/090749396},
  keywords = {traveling salesman problem; approximation algorithms; metric spanners;
	global notion of dimension},
  noteurl = {http://link.aip.org/link/?SMJ/41/587/1},
  publisher = {SIAM}
}

@ARTICLE{ChanG06,
  author = {T.-H. Hubert Chan and Anupam Gupta},
  title = {Small Hop-diameter Sparse Spanners for Doubling Metrics},
  journal = {Discrete {\&} Computational Geometry},
  year = {2009},
  volume = {41},
  pages = {28-44},
  number = {1},
  doi = {http://dx.doi.org/10.1007/s00454-008-9115-5}
}

@INPROCEEDINGS{CG08,
  author = {T.-H. Hubert Chan and Anupam Gupta},
  title = {Approximating {TSP} on metrics with bounded global growth},
  booktitle = soda,
  year = {2008},
  pages = {690--699},
  doi = {http://doi.acm.org/10.1145/1347082.1347158}
}

@INPROCEEDINGS{ChanG06-proc,
  author = {T.-H. Hubert Chan and Anupam Gupta},
  title = {Small hop-diameter sparse spanners for doubling metrics},
  booktitle = soda,
  year = {2006},
  pages = {70-78},
  doi = {http://doi.acm.org/10.1145/1109557.1109566}
}

@INPROCEEDINGS{CGMZ05,
  author = {T.-H. Hubert Chan and Anupam Gupta and Bruce M. Maggs and Shuheng
	Zhou},
  title = {On Hierarchical Routing in Doubling Metrics},
  booktitle = soda,
  year = {2005},
  pages = {762--771},
  doi = {http://doi.acm.org/10.1145/1070432.1070540}
}

@ARTICLE{ChanGT10,
  author = {T.-H. Hubert Chan and Anupam Gupta and Kunal Talwar},
  title = {Ultra-low-dimensional embeddings for doubling metrics},
  journal = {J. ACM},
  year = {2010},
  volume = {57},
  number = {4},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1734213.1734215}
}

@INPROCEEDINGS{CGT08,
  author = {T.-H. Hubert Chan and Anupam Gupta and Kunal Talwar},
  title = {Ultra-low-dimensional embeddings for doubling metrics},
  booktitle = soda,
  year = {2008},
  pages = {333--342},
  doi = {http://doi.acm.org/10.1145/1347082.1347119}
}

@ARTICLE{CGR05,
  author = {Chawla, Shuchi and Gupta, Anupam and R{\"a}cke, Harald},
  title = {Embeddings of negative-type metrics and an improved approximation
	to generalized sparsest cut},
  journal = {ACM Trans. Algorithms},
  year = {2008},
  volume = {4},
  pages = {Art. 22, 18},
  number = {2},
  doi = {http://doi.acm.org/10.1145/1361192.1361199},
  fjournal = {ACM Transactions on Algorithms},
  issn = {1549-6325},
  mrclass = {68R10 (54E35)},
  mrnumber = {MR2419119}
}

@INPROCEEDINGS{CGR05-proc,
  author = {Shuchi Chawla and Anupam Gupta and Harald R{\"a}cke},
  title = {Improved Approximations for {Sparsest} {Cut}},
  booktitle = soda,
  year = {2005},
  pages = {102--111},
  doi = {http://doi.acm.org/10.1145/1070432.1070447}
}

@ARTICLE{CEGS11-talg,
  author = {Chandra Chekuri and Guy Even and Anupam Gupta and Danny Segev},
  title = {Set connectivity problems in undirected graphs and the directed {S}teiner
	network problem},
  journal = {ACM Transactions on Algorithms},
  year = {2011},
  volume = {7},
  pages = {18},
  number = {2},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1921659.1921664}
}

@INPROCEEDINGS{CEGS08,
  author = {Chandra Chekuri and Guy Even and Anupam Gupta and Danny Segev},
  title = {Set connectivity problems in undirected graphs and the directed {S}teiner
	network problem},
  booktitle = soda,
  year = {2008},
  pages = {532--541},
  doi = {http://doi.acm.org/10.1145/1347082.1347141}
}

@ARTICLE{CGKbidir05,
  author = {Chekuri, Chandra and Gupta, Anupam and Kumar, Amit},
  title = {On a bidirected relaxation for the {Multiway} {Cut} problem},
  journal = {Discrete Appl. Math.},
  year = {2005},
  volume = {150},
  pages = {67--79},
  number = {1-3},
  doi = {http://dx.doi.org/10.1016/j.dam.2005.04.003},
  fjournal = {Discrete Applied Mathematics. Combinatorial Algorithms, Optimization
	and Computer Science}
}

@ARTICLE{CGKNR01,
  author = {Chekuri, Chandra and Gupta, Anupam and Kumar, Amit and Naor, Joseph
	(Seffi) and Raz, Danny},
  title = {Building edge-failure resilient networks},
  journal = {Algorithmica},
  year = {2005},
  volume = {43},
  pages = {17--41},
  number = {1-2},
  coden = {ALGOEJ},
  doi = {http://dx.doi.org/10.1007/s00453-005-1156-z},
  fjournal = {Algorithmica. An International Journal in Computer Science},
  issn = {0178-4617},
  mrclass = {68M10 (68M15)},
  mrnumber = {MR2162270}
}

@INPROCEEDINGS{CGKNR01-conf,
  author = {Chandra Chekuri and Anupam Gupta and Amit Kumar and Joseph (Seffi)
	Naor and Danny Raz},
  title = {Building edge-failure resilient networks},
  booktitle = ipco,
  year = {2002},
  volume = {2337},
  series = lncs,
  pages = {439--456},
  doi = {http://dx.doi.org/10.1007/3-540-47867-1_31}
}

@ARTICLE{CGNRS01,
  author = {Chekuri, Chandra and Gupta, Anupam and Newman, Ilan and Rabinovich,
	Yuri and Sinclair, Alistair},
  title = {Embedding {$k$}-outerplanar graphs into {$\ell_1$}},
  journal = {SIAM J. Discrete Math.},
  year = {2006},
  volume = {20},
  pages = {119--136},
  number = {1},
  doi = {http://dx.doi.org/10.1137/S0895480102417379},
  fjournal = {SIAM Journal on Discrete Mathematics}
}

@INPROCEEDINGS{CGNRS01-conf,
  author = {Chandra Chekuri and Anupam Gupta and Ilan Newman and Yuri Rabinovich
	and Alistair Sinclair},
  title = {Embedding $k$-outerplanar graphs into $\ell_1$},
  booktitle = soda,
  year = {2003},
  pages = {527--536},
  doi = {http://doi.acm.org/10.1145/644108.644197}
}

@INPROCEEDINGS{CGNS05-proc,
  author = {Julia Chuzhoy and Anupam Gupta and Joseph (Seffi) Naor and Amitabh
	Sinha},
  title = {On the Approximability of Network Design Problems},
  booktitle = soda,
  year = {2005},
  pages = {943--951},
  doi = {http://doi.acm.org/10.1145/1070432.1070568}
}

@ARTICLE{CGNS05,
  author = {Chuzhoy, Julia and Gupta, Anupam and Naor, Joseph and Sinha, Amitabh},
  title = {On the approximability of some network design problems},
  journal = {ACM Trans. Algorithms},
  year = {2008},
  volume = {4},
  pages = {Art. 23, 17},
  number = {2},
  doi = {http://doi.acm.org/10.1145/1361192.1361200},
  fjournal = {ACM Transactions on Algorithms},
  issn = {1549-6325},
  mrclass = {68W05 (05C85 68M10 68R10 68W25 90B10)},
  mrnumber = {MR2419120}
}

@INPROCEEDINGS{CEGMS13,
  author = {Marek Cygan and Matthias Englert and Anupam Gupta and Marcin Mucha
	and Piotr Sankowski},
  title = {Catch Them If You Can: How to Serve Impatient Users},
  booktitle = {Innovations in Theoretical Computer Science Conference},
  year = {2013},
  month = {Jan},
  doi = {http://doi.acm.org/10.1145/2422436.2422489}
}

@ARTICLE{DG99,
  author = {Sanjoy Dasgupta and Anupam Gupta},
  title = {An elementary proof of a theorem of {Johnson} and {Lindenstrauss}},
  journal = {Random Structures Algorithms},
  year = {2003},
  volume = {22},
  pages = {60--65},
  number = {1},
  doi = {http://dx.doi.org/10.1002/rsa.10073},
  fjournal = {Random Structures \& Algorithms},
  issn = {1042-9832},
  mrclass = {60C05 (52B55)},
  mrnumber = {1 943 859}
}

@TECHREPORT{DG99-old,
  author = {Sanjoy Dasgupta and Anupam Gupta},
  title = {A simple proof of the {Johnson-Lindenstrauss} lemma},
  institution = {International Computer Science Institute},
  year = {1999},
  number = {99-006},
  url = {http://www.icsi.berkeley.edu/cgi-bin/pubs/publication.pl?ID=1162}
}

@INPROCEEDINGS{DGR06,
  author = {Kedar Dhamdhere and Anupam Gupta and Harald R{\"a}cke},
  title = {Improved embeddings of graph metrics into random trees (article withdrawn)},
  booktitle = soda,
  year = {2006},
  pages = {61-69},
  doi = {http://doi.acm.org/10.1145/1109557.1109565}
}

@ARTICLE{DGRstacs04,
  author = {Kedar Dhamdhere and Anupam Gupta and R. Ravi},
  title = {Approximation Algorithms for Minimizing Average Distortion},
  journal = {Theory of Computing Systems},
  year = {2006},
  volume = {39},
  pages = {93--111},
  number = {1},
  note = {(Preliminary version in {\em 21st STACS}, 2004)",},
  doi = {http://dx.doi.org/10.1007/s00224-005-1259-6}
}

@INPROCEEDINGS{DGRstacs04-conf,
  author = {Kedar Dhamdhere and Anupam Gupta and R. Ravi},
  title = {Approximation Algorithms for Minimizing Average Distortion},
  booktitle = stacs,
  year = {2004},
  volume = {2996},
  series = lncs,
  pages = {234--245},
  doi = {http://dx.doi.org/10.1007/b96012}
}

@INPROCEEDINGS{DG13-interdict,
  author = {Michael Dinitz and Anupam Gupta},
  title = {Packing Interdiction and Partial Covering Problems},
  booktitle = ipco,
  year = {2013},
  month = {Apr},
  doi = {http://dx.doi.org/10.1007/978-3-642-36694-9_14}
}

@INPROCEEDINGS{EnglertGKRTT10,
  author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald
	R{\"a}cke and Inbal Talgam-Cohen and Kunal Talwar},
  title = {Vertex Sparsifiers: New Results from Old Techniques},
  booktitle = {APPROX-RANDOM},
  year = {2010},
  pages = {152-165},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-15369-3_12}
}

@ARTICLE{EnglertGKRTT10-arxiv,
  author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald
	R{\"a}cke and Inbal Talgam-Cohen and Kunal Talwar},
  title = {Vertex Sparsifiers: New Results from Old Techniques},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1006.4586},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1006.4586}
}

@INPROCEEDINGS{FGS13,
  author = {Zachary Friggstad and Anupam Gupta and Mohit Singh},
  title = {An Improved Integrality Gap for Asymmetric TSP Paths},
  booktitle = ipco,
  year = {2013},
  month = {Apr},
  doi = {http://dx.doi.org/10.1007/978-3-642-36694-9_16}
}

@ARTICLE{FGS13-arxiv,
  author = {Zachary Friggstad and Anupam Gupta and Mohit Singh},
  title = {An Improved Integrality Gap for Asymmetric TSP Paths},
  journal = {CoRR},
  year = {2013},
  volume = {abs/1302.3145},
  ee = {http://arxiv.org/abs/1302.3145},
  url = {http://arxiv.org/abs/1302.3145}
}

@INPROCEEDINGS{GGLS08,
  author = {Naveen Garg and Anupam Gupta and Stefano Leonardi and Piotr Sankowski},
  title = {Stochastic analyses for online combinatorial optimization problems},
  booktitle = soda,
  year = {2008},
  pages = {942--951},
  doi = {http://doi.acm.org/10.1145/1347082.1347185}
}

@ARTICLE{Gitter2010,
  author = {Anthony Gitter and Judith Klein-Seetharaman and Anupam Gupta and
	Ziv Bar-Joseph},
  title = {Discovering pathways by orienting edges in protein interaction networks.},
  journal = {Nucleic Acids Res},
  year = {2010},
  month = {Nov},
  abstract = {Modern experimental technology enables the identification of the sensory
	proteins that interact with the cells' environment or various pathogens.
	Expression and knockdown studies can determine the downstream effects
	of these interactions. However, when attempting to reconstruct the
	signaling networks and pathways between these sources and targets,
	one faces a substantial challenge. Although pathways are directed,
	high-throughput protein interaction data are undirected. In order
	to utilize the available data, we need methods that can orient protein
	interaction edges and discover high-confidence pathways that explain
	the observed experimental outcomes. We formalize the orientation
	problem in weighted protein interaction graphs as an optimization
	problem and present three approximation algorithms based on either
	weighted Boolean satisfiability solvers or probabilistic assignments.
	We use these algorithms to identify pathways in yeast. Our approach
	recovers twice as many known signaling cascades as a recent unoriented
	signaling pathway prediction technique and over 13 times as many
	as an existing network orientation algorithm. The discovered paths
	match several known signaling pathways and suggest new mechanisms
	that are not currently present in signaling databases. For some pathways,
	including the pheromone signaling pathway and the high-osmolarity
	glycerol pathway, our method suggests interesting and novel components
	that extend current annotations.},
  doi = {http://dx.doi.org/10.1093/nar/gkq1207},
  institution = {Computer Science Department, Carnegie Mellon University and Department
	of Structural Biology, University of Pittsburgh School of Medicine,
	Pittsburgh, PA, USA.},
  language = {eng},
  medline-pst = {aheadofprint},
  pii = {gkq1207},
  pmid = {21109539}
}

@INPROCEEDINGS{GGKT08,
  author = {Daniel Golovin and Anupam Gupta and Amit Kumar and Kanat Tangwongsan},
  title = {All-Norms and All-$L_p$-Norms Approximation Algorithms},
  booktitle = fsttcs,
  year = {2008},
  volume = {08004},
  series = {Dagstuhl Seminar Proceedings},
  doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1753},
  url = {http://drops.dagstuhl.de/opus/volltexte/2008/1753/}
}

@INPROCEEDINGS{GGMOR06,
  author = {Daniel Golovin and Anupam Gupta and Bruce M. Maggs and Florian Oprea
	and Michael K. Reiter},
  title = {Quorum placement in networks: minimizing network congestion},
  booktitle = podc,
  year = {2006},
  pages = {16-25},
  doi = {http://doi.acm.org/10.1145/1146381.1146388}
}

@INPROCEEDINGS{GGLR07,
  author = {Vineet Goyal and Anupam Gupta and Stefano Leonardi and R. Ravi},
  title = {Pricing Tree Access Networks with Connected Backbones},
  booktitle = esa,
  year = {2007},
  pages = {498--509},
  doi = {http://dx.doi.org/10.1007/978-3-540-75520-3_45}
}

@INPROCEEDINGS{GGLMSS08,
  author = {Grandoni, Fabrizio and Gupta, Anupam and Leonardi, Stefano and Miettinen,
	Pauli and Sankowski, Piotr and Singh, Mohit},
  title = {Set Covering with our Eyes Closed},
  booktitle = focs,
  year = {2008},
  pages = {347-356},
  month = {Oct.},
  doi = {http://dx.doi.org/10.1109/FOCS.2008.31},
  issn = {0272-5428},
  keywords = {computational complexity, graph theory, optimisation, set theory,
	stochastic processesa-priori optimization, computational complexity,
	disc-covering problem, stochastic online algorithm, universal multicut
	problem, universal set cover problem}
}

@INPROCEEDINGS{GGK13-steiner,
  author = {Albert Gu and Anupam Gupta and Amit Kumar},
  title = {The Power of Deferral: Maintaining a Constant-Competitive Steiner
	Tree Online},
  booktitle = stoc,
  year = {2013},
  month = {Jun},
}

@INPROCEEDINGS{GupDirMulticut01,
  author = {Anupam Gupta},
  title = {Improved Approximations for Directed Multicut},
  booktitle = soda,
  year = {2003},
  pages = {454--455},
  doi = {http://doi.acm.org/10.1145/644108.644181}
}

@ARTICLE{Gup00-jalg,
  author = {Anupam Gupta},
  title = {Improved bandwidth approximation for trees and chordal graphs},
  journal = {J. Algorithms},
  year = {2001},
  volume = {40},
  pages = {24--36},
  number = {1},
  note = {(Preliminary version in {\em 11th SODA}, 2000)},
  coden = {JOALDV},
  doi = {http://dx.doi.org/10.1006/jagm.2000.1118},
  fjournal = {Journal of Algorithms},
  issn = {0196-6774},
  mrclass = {68R10 (05C85 68W25)},
  mrnumber = {2002d:68079}
}

@INPROCEEDINGS{Gup01,
  author = {Anupam Gupta},
  title = {Steiner points in tree metrics don't (really) help},
  booktitle = soda,
  year = {2001},
  pages = {220--227},
  doi = {http://doi.acm.org/10.1145/365411.365448},
  mrclass = {05C85 (51E10)},
  mrnumber = {1 958 411}
}

@INPROCEEDINGS{Gup00,
  author = {Anupam Gupta},
  title = {Improved bandwidth approximation for trees},
  booktitle = soda,
  year = {2000},
  pages = {788--793},
  address = {New York},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/338219.338640},
  mrclass = {68R10 (68W20 68W25)},
  mrnumber = {1 755 540}
}

@ARTICLE{Gup99,
  author = {Anupam Gupta},
  title = {Embedding tree metrics into low-dimensional {Euclidean} spaces},
  journal = {Discrete Comput. Geom.},
  year = {2000},
  volume = {24},
  pages = {105--116},
  number = {1},
  note = {(Preliminary version in {\em 31st STOC}, 1999)},
  coden = {DCGEER},
  doi = {http://dx.doi.org/10.1006/jagm.2000.1118},
  fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics
	and Computer Science},
  issn = {0179-5376},
  mrclass = {68U05 (54C25 54E35)},
  mrnumber = {2001b:68144}
}

@PHDTHESIS{Gupthesis,
  author = {Anupam Gupta},
  title = {Embeddings of Finite Metrics},
  school = {University of California, Berkeley},
  year = {2000},
  month = {Aug.},
}

@INPROCEEDINGS{Gup99-conf,
  author = {Anupam Gupta},
  title = {Embedding tree metrics into low dimensional {Euclidean} spaces},
  booktitle = stoc,
  year = {1999},
  pages = {694--700},
  address = {New York},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/301250.301434},
  mrclass = {68U05 (54C25 54E35 65D18)},
  mrnumber = {1 798 093}
}

@ARTICLE{BJG08,
  author = {Gupta, Anupam and Bar-Joseph, Ziv},
  title = {Extracting Dynamics from Static Cancer Expression Data},
  journal = {IEEE/ACM Trans. Comput. Biol. Bioinformatics},
  year = {2008},
  volume = {5},
  pages = {172--182},
  number = {2},
  address = {Los Alamitos, CA, USA},
  doi = {http://dx.doi.org/10.1109/TCBB.2007.70233},
  issn = {1545-5963},
  publisher = {IEEE Computer Society Press}
}

@INPROCEEDINGS{GHK07,
  author = {Anupam Gupta and MohammadTaghi Hajiaghayi and Amit Kumar},
  title = {Stochastic {S}teiner Tree with Non-Uniform Inflation},
  booktitle = approx,
  year = {2007},
  pages = {134--148},
  doi = {http://dx.doi.org/10.1007/978-3-540-74208-1_10}
}

@INPROCEEDINGS{GHNR07,
  author = {Anupam Gupta and MohammadTaghi Hajiaghayi and Viswanath Nagarajan
	and R. Ravi},
  title = {Dial a Ride from $k$-Forest},
  booktitle = esa,
  year = {2007},
  pages = {241--252},
  doi = {http://dx.doi.org/10.1007/978-3-540-75520-3_23}
}

@ARTICLE{GHNR-arxiv,
  author = {Anupam Gupta and MohammadTaghi Hajiaghayi and Viswanath Nagarajan
	and R. Ravi},
  title = {Dial a Ride from k-forest},
  journal = {CoRR},
  year = {2007},
  volume = {abs/0707.0648},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/0707.0648}
}

@INPROCEEDINGS{GHR06,
  author = {Anupam Gupta and MohammadTaghi Hajiaghayi and Harald R{\"a}cke},
  title = {Oblivious network design},
  booktitle = soda,
  year = {2006},
  pages = {970-979},
  doi = {http://doi.acm.org/10.1145/1109557.1109665}
}

@ARTICLE{GHNR10,
  author = {Anupam Gupta and Mohammad Taghi Hajiaghayi and Viswanath Nagarajan
	and R. Ravi},
  title = {Dial a Ride from {\it k}-forest},
  journal = {ACM Transactions on Algorithms},
  year = {2010},
  volume = {6},
  number = {2},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1721837.1721857}
}

@INPROCEEDINGS{GHRU11-stoc,
  author = {Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman},
  title = {Privately Releasing Conjunctions and the Statistical Query Barrier},
  booktitle = stoc,
  year = {2011},
  pages = {803-812},
  month = {May},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1993636.1993742}
}

@ARTICLE{GHRU10-arxiv,
  author = {Anupam Gupta and Moritz Hardt and Aaron Roth and Jonathan Ullman},
  title = {Privately Releasing Conjunctions and the Statistical Query Barrier},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1011.1296},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1011.1296}
}

@INPROCEEDINGS{GIKMP12-soda,
  author = {Anupam Gupta and Sungjin Im and Ravishankar Krishnaswamy and Benjamin
	Moseley and Kirk Pruhs},
  title = {Scheduling Heterogeneous Processors Isn't As Easy As You Think},
  booktitle = {SODA},
  year = {2012},
  pages = {1242--1253},
  month = {Jan},
  url = {http://dl.acm.org/citation.cfm?id=2095116.2095214}
}

@INPROCEEDINGS{GIKMP10,
  author = {Anupam Gupta and Sungjin Im and Ravishankar Krishnaswamy and Benjamin
	Moseley and Kirk Pruhs},
  title = {Scheduling jobs with varying parallelizability to reduce variance},
  booktitle = {SPAA},
  year = {2010},
  pages = {11-20},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1810479.1810482}
}

@ARTICLE{GK10-survey,
  author = {Anupam Gupta and Jochen K\"{o}nemann},
  title = {Approximation algorithms for network design: A survey},
  journal = {Surveys in Operations Research and Management Science},
  year = {2011},
  volume = {16},
  pages = {3 - 20},
  number = {1},
  doi = {http://dx.doi.org/10.1016/j.sorms.2010.06.001},
  issn = {1876-7354}
}

@INPROCEEDINGS{GKLRS07,
  author = {Anupam Gupta and Jochen K\"{o}nemann and Stefano Leonardi and R.
	Ravi and Guido Sch\"{a}fer},
  title = {An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner
	Forest Problem},
  booktitle = soda,
  year = {2007},
  pages = {1153--1162},
  doi = {http://doi.acm.org/10.1145/1109557.1109569}
}

@INPROCEEDINGS{GKL03,
  author = {Anupam Gupta and Robert Krauthgamer and James R.\ Lee},
  title = {Bounded geometries, fractals, and low--distortion embeddings},
  booktitle = focs,
  year = {2003},
  pages = {534--543},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238226}
}

@INPROCEEDINGS{GKKS09,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Danny
	Segev},
  title = {Scheduling with Outliers},
  booktitle = approx,
  year = {2009},
  pages = {149-162},
  doi = {http://dx.doi.org/10.1007/978-3-642-03685-9_12}
}

@ARTICLE{GKKS-arxiv,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Amit Kumar and Danny
	Segev},
  title = {Scheduling with Outliers},
  journal = {CoRR},
  year = {2009},
  volume = {abs/0906.2020},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/0906.2020}
}

@ARTICLE{GKMR11-arxiv,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and
	R. Ravi},
  title = {Approximation Algorithms for Correlated Knapsacks and Non-Martingale
	Bandits},
  journal = {CoRR},
  year = {2011},
  volume = {abs/1102.3749},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1102.3749}
}

@INPROCEEDINGS{GKMR11-focs,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Marco Molinaro and
	R. Ravi},
  title = {Approximation Algorithms for Correlated Knapsacks and Non-Martingale
	Bandits},
  booktitle = focs,
  year = {2011},
  pages = {827--836},
  month = {Nov},
  doi = {http://dx.doi.org/10.1109/FOCS.2011.48}
}

@INPROCEEDINGS{GKNR12-soda,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Viswanath Nagarajan
	and R. Ravi},
  title = {Approximation Algorithms for Stochastic Orienteering},
  booktitle = {SODA},
  year = {2012},
  month = {Jan},
  url = {http://dl.acm.org/citation.cfm?id=2095116.2095237}
}

@ARTICLE{GKNR10-arxiv,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Viswanath Nagarajan
	and R. Ravi},
  title = {Approximation Algorithms for Optimal Decision Trees and Adaptive
	TSP Problems},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1003.0722},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1003.0722}
}

@INPROCEEDINGS{GKP11-waoa,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs},
  title = {Online Primal-Dual For Non-linear Optimization with Applications
	to Speed Scaling},
  booktitle = {Workshop on Approximation and Online Algorithms},
  year = {2012},
  month = {Sep},
}

@ARTICLE{GKP10-arxiv,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs},
  title = {Scalably Scheduling Power-Heterogeneous Processors},
  journal = {CoRR},
  year = {2011},
  volume = {abs/1105.3748},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1105.3748}
}

@ARTICLE{GKP10-suscom,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs},
  title = {Nonclairvoyantly scheduling power-heterogeneous processors},
  journal = {Sustainable Computing: Informatics and Systems},
  year = {2011},
  volume = {1},
  pages = {248--255},
  number = {3},
  doi = {http://dx.doi.org/10.1016/j.suscom.2011.05.007},
  issn = {2210-5379},
  noteurl = {http://www.sciencedirect.com/science/article/pii/S2210537911000412}
}

@ARTICLE{GKP11-arxiv,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs},
  title = {Online Primal-Dual For Non-linear Optimization with Applications
	to Speed Scaling},
  journal = {CoRR},
  year = {2011},
  volume = {abs/1109.5931},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1109.5931}
}

@INPROCEEDINGS{GKP10,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and Kirk Pruhs},
  title = {Scalably Scheduling Power-Heterogeneous Processors},
  booktitle = {ICALP (1)},
  year = {2010},
  pages = {312-323},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-14165-2_27}
}

@INPROCEEDINGS{GKP10-green,
  author = {Gupta, Anupam and Krishnaswamy, Ravishankar and Pruhs, Kirk},
  title = {Nonclairvoyantly scheduling power-heterogeneous processors},
  booktitle = {International Green Computing Conference},
  year = {2010},
  pages = {165 -173},
  month = {Aug.},
  abstract = {We show that a natural nonclairvoyant online algorithm for scheduling
	jobs on a power-heterogeneous multiprocessor is bounded-speed bounded-competitive
	for the objective of flow plus energy.},
  doi = {http://doi.acm.org/10.1109/GREENCOMP.2010.5598311},
  keywords = {flow plus energy objective;nonclairvoyant online algorithm;power-heterogeneous
	multiprocessor;scheduling;multiprocessing systems;scheduling;}
}

@ARTICLE{gkr09-sicomp,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and R. Ravi},
  title = {Online and Stochastic Survivable Network Design},
  journal = {SIAM J. Comput.},
  year = {2012},
  volume = {41},
  pages = {1649-1672},
  number = {6},
  doi = {http://dx.doi.org/10.1137/09076725X}
}

@INPROCEEDINGS{gkr-soda10,
  author = {Anupam Gupta and Ravishankar Krishnaswamy and R. Ravi},
  title = {Tree Embeddings for Two-Edge-Connected Network Design},
  booktitle = {SODA},
  year = {2010},
  pages = {1521-1538},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1873601.1873725},
  ee = {http://www.siam.org/proceedings/soda/2010/SODA10_124_guptaa.pdf}
}

@INPROCEEDINGS{GKR-online09,
  author = {Gupta, Anupam and Krishnaswamy, Ravishankar and Ravi, R.},
  title = {Online and stochastic survivable network design},
  booktitle = {STOC},
  year = {2009},
  pages = {685--694},
  address = {New York, NY, USA},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/1536414.1536507},
  isbn = {978-1-60558-506-2},
  location = {Bethesda, MD, USA}
}

@INPROCEEDINGS{GK-ssf09,
  author = {Gupta, Anupam and Kumar, Amit},
  title = {A constant-factor approximation for stochastic Steiner forest},
  booktitle = {STOC},
  year = {2009},
  pages = {659--668},
  address = {New York, NY, USA},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/1536414.1536504},
  isbn = {978-1-60558-506-2},
  location = {Bethesda, MD, USA}
}

@INPROCEEDINGS{GKwinner05,
  author = {Anupam Gupta and Amit Kumar},
  title = {Where's the Winner? Max-Finding and Sorting with Metric Costs},
  booktitle = approx,
  year = {2005},
  volume = {3624},
  series = lncs,
  pages = {74-85},
  doi = {http://dx.doi.org/10.1007/11538462_7}
}

@INPROCEEDINGS{GKsort01,
  author = {Anupam Gupta and Amit Kumar},
  title = {Sorting and selection with structured costs},
  booktitle = focs,
  year = {2001},
  pages = {416--425},
  publisher = {IEEE Computer Soc., Los Alamitos, CA},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2001.959916},
  mrclass = {68P10 (68W40)},
  mrnumber = {1 948 730}
}

@INPROCEEDINGS{GKKRY01,
  author = {Anupam Gupta and Amit Kumar and Jon M. Kleinberg and Rajeev Rastogi
	and B{\"u}lent Yener},
  title = {Provisioning a {Virtual Private Network}: {A} Network Design Problem
	for Multicommodity Flow},
  booktitle = stoc,
  year = {2001},
  pages = {389--398},
  doi = {http://doi.acm.org/10.1145/380752.380830}
}

@ARTICLE{GKPR-JACM,
  author = {Gupta, Anupam and Kumar, Amit and P{\'a}l, Martin and Roughgarden,
	Tim},
  title = {Approximation via cost sharing: simpler and better approximation
	algorithms for network design},
  journal = {J. ACM},
  year = {2007},
  volume = {54},
  pages = {Art. 11, 38 pp.},
  number = {3},
  doi = {http://doi.acm.org/10.1145/1236457.1236458},
  fjournal = {Journal of the ACM},
  issn = {0004-5411},
  mrclass = {68W25 (68M10)},
  mrnumber = {MR2314253}
}

@INPROCEEDINGS{GKPRmrob03,
  author = {Anupam Gupta and Amit Kumar and Martin P{\'a}l and Tim Roughgarden},
  title = {Approximations via Cost-Sharing},
  booktitle = focs,
  year = {2003},
  pages = {606--615},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238233}
}

@ARTICLE{GKmpls01,
  author = {Gupta, Anupam and Kumar, Amit and Rastogi, Rajeev},
  title = {Traveling with a {P}ez dispenser (or, routing issues in {MPLS})},
  journal = {SIAM J. Comput.},
  year = {2004},
  volume = {34},
  pages = {453--474},
  number = {2},
  doi = {http://dx.doi.org/10.1137/S0097539702409927},
  fjournal = {SIAM Journal on Computing},
  issn = {0097-5397},
  mrclass = {68M12 (05C78 05C85 68W40)},
  mrnumber = {MR2124013 (2006b:68011)},
  mrreviewer = {Ion-Lilian Florea}
}

@INPROCEEDINGS{GKRinfocom03,
  author = {Anupam Gupta and Amit Kumar and Rajeev Rastogi},
  title = {Exploring the Trade-off between Label Size and Stack Depth in {MPLS}
	Routing},
  booktitle = infocom,
  year = {2003},
  volume = {1},
  pages = {544--554},
  file = {:http\://www.ieee-infocom.org/2003/papers/14_01.PDF:URL}
}

@INPROCEEDINGS{GKmpls01-conf,
  author = {Anupam Gupta and Amit Kumar and Rajeev Rastogi},
  title = {Traveling with a {Pez} dispenser (or, routing issues in {MPLS})},
  booktitle = focs,
  year = {2001},
  pages = {148--157},
  publisher = {IEEE Computer Soc., Los Alamitos, CA},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2001.959889},
  mrclass = {68M10 (68M12 68U35)},
  mrnumber = {1 948 703}
}

@INPROCEEDINGS{GKRstoc03,
  author = {Anupam Gupta and Amit Kumar and Tim Roughgarden},
  title = {Simpler and Better Approximation Algorithms for Network Design},
  booktitle = stoc,
  year = {2003},
  pages = {365--372},
  doi = {http://doi.acm.org/10.1145/780542.780597},
  file = {:http\://www.siam.org/proceedings/soda/2010/SODA10_125_bansaln.pdf:URL}
}

@INPROCEEDINGS{GKTspaa03,
  author = {Anupam Gupta and Amit Kumar and Mikkel Thorup},
  title = {Tree based {MPLS} routing},
  booktitle = spaa,
  year = {2003},
  pages = {193--199},
  publisher = {ACM Press},
  doi = {http://doi.acm.org/10.1145/777412.777443},
  isbn = {1-58113-661-7},
  location = {San Diego, California, USA}
}

@INPROCEEDINGS{GLLWX10,
  author = {Anupam Gupta and John Lafferty and Han Liu and Larry Wasserman and
	Min Xu},
  title = {Forest Density Estimation},
  booktitle = {COLT},
  year = {2010},
  pages = {394--406},
  abstract = {We study graph estimation and density estimation in high dimensions,
	using a family of density estimators based on forest structured undirected
	graphical models. For density estimation, we do not assume the true
	distribution corresponds to a forest; rather, we form kernel density
	estimates of the bivariate and univariate marginals, and apply Kruskal's
	algorithm to estimate the optimal forest on held out data. We prove
	an oracle inequality on the excess risk of the resulting estimator
	relative to the risk of the best forest. For graph estimation, we
	consider the problem of estimating forests with restricted tree sizes.
	We prove that finding a maximum weight spanning forest with restricted
	tree size is NP-hard, and develop an approximation algorithm for
	this problem. Viewing the tree size as a complexity parameter, we
	then select a forest using cross-validation, and prove bounds on
	excess risk and structure selection consistency of the procedure.},
  file = {:http\://www.colt2010.org/papers/074lafferty.pdf:URL},
  url = {http://www.colt2010.org/papers.html}
}

@INPROCEEDINGS{GL12-line,
  author = {Anupam Gupta and Kevin Lewi},
  title = {The Online Metric Matching Problem for Doubling Metrics},
  booktitle = {ICALP (1)},
  year = {2012},
  month = {Jul},
  doi = {http://dx.doi.org/10.1007/978-3-642-31594-7_36}
}

@INPROCEEDINGS{GLMRT-soda10,
  author = {Anupam Gupta and Katrina Ligett and Frank McSherry and Aaron Roth
	and Kunal Talwar},
  title = {Differentially Private Combinatorial Optimization},
  booktitle = {SODA},
  year = {2010},
  pages = {1106-1125},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1873601.1873691},
  ee = {http://www.siam.org/proceedings/soda/2010/SODA10_090_guptaa.pdf}
}

@ARTICLE{GLMRT-arxiv,
  author = {Anupam Gupta and Katrina Ligett and Frank McSherry and Aaron Roth
	and Kunal Talwar},
  title = {Differentially Private Approximation Algorithms},
  journal = {CoRR},
  year = {2009},
  volume = {abs/0903.4510},
  url = {http://arxiv.org/abs/0903.4510}
}

@INPROCEEDINGS{GuptaMOR05,
  author = {Anupam Gupta and Bruce M. Maggs and Florian Oprea and Michael K.
	Reiter},
  title = {Quorum placement in networks to minimize access delays},
  booktitle = podc,
  year = {2005},
  pages = {87-96},
  doi = {http://doi.acm.org/10.1145/1073829}
}

@INPROCEEDINGS{GN13-probe,
  author = {Anupam Gupta and Viswanath Nagarajan},
  title = {A Stochastic Probing Problem with Applications},
  booktitle = ipco,
  year = {2013},
  month = {Apr},
  doi = {http://dx.doi.org/10.1007/978-3-642-36694-9_18}
}

@ARTICLE{GNV13-probe-arxiv,
  author = {Anupam Gupta and Viswanath Nagarajan},
  title = {A Stochastic Probing Problem with Applications},
  journal = {CoRR},
  year = {2013},
  volume = {1302.5913},
  month = {Apr},
  ee = {http://arxiv.org/abs/1302.5913},
  url = {http://arxiv.org/abs/1302.5913}
}

@ARTICLE{GN12-arxiv,
  author = {Anupam Gupta and Viswanath Nagarajan},
  title = {Approximating Sparse Covering Integer Programs Online},
  journal = {CoRR},
  year = {2012},
  volume = {abs/1205.0175},
  month = {May},
  ee = {http://arxiv.org/abs/1205.0175},
  url = {http://arxiv.org/abs/1205.0175}
}

@INPROCEEDINGS{GN12-online,
  author = {Anupam Gupta and Viswanath Nagarajan},
  title = {Approximating Sparse Covering Integer Programs Online},
  booktitle = {ICALP (1)},
  year = {2012},
  month = {Jul},
  doi = {http://dx.doi.org/10.1007/978-3-642-31594-7_37}
}

@ARTICLE{GNR11-vrp,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Approximation Algorithms for VRP with Stochastic Demands},
  journal = {Operations Research},
  year = {2012},
  volume = {60},
  pages = {123--137},
  number = {1},
  doi = {http://dx.doi.org/10.1287/opre.1110.0967},
  noteurl = {http://or.journal.informs.org/content/60/1/123.abstract}
}

@INPROCEEDINGS{GNR10-robust,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Thresholded Covering Algorithms for Robust and Max-min Optimization},
  booktitle = {ICALP (1)},
  year = {2010},
  pages = {262-274},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-14165-2_23}
}

@INPROCEEDINGS{GNR10-stsp,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Approximation Algorithms for Optimal Decision Trees and Adaptive
	TSP Problems},
  booktitle = {ICALP (1)},
  year = {2010},
  pages = {690-701},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-14165-2_58}
}

@ARTICLE{GNR-reqcut,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Improved Approximation Algorithms for Requirement Cut},
  journal = {Operations Research Letters},
  year = {2010},
  volume = {38},
  pages = {322-325},
  number = {4},
  doi = {http://dx.doi.org/10.1016/j.orl.2010.02.009}
}

@ARTICLE{GNRrobust2-arxiv,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty
	Sets},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1012.4962},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1012.4962}
}

@ARTICLE{GNRrobust-arxiv,
  author = {Anupam Gupta and Viswanath Nagarajan and R. Ravi},
  title = {Thresholded Covering Algorithms for Robust and Max-Min Optimization},
  journal = {CoRR},
  year = {2009},
  volume = {abs/0912.1045},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/0912.1045}
}

@INPROCEEDINGS{GNV13,
  author = {Anupam Gupta and Viswanath Nagarajan and Vijay V. Vazirani},
  title = {Thrifty Algorithms for Multistage Robust Optimization},
  booktitle = ipco,
  year = {2013},
  month = {Apr},
  doi = {http://dx.doi.org/10.1007/978-3-642-36694-9_19}
}

@ARTICLE{GNV13-arxiv,
  author = {Anupam Gupta and Viswanath Nagarajan and Vijay V. Vazirani},
  title = {Thrifty Algorithms for Multistage Robust Optimization},
  journal = {CoRR},
  year = {2013},
  volume = {1302.5445},
  month = {Apr},
  ee = {http://arxiv.org/abs/1302.5445},
  url = {http://arxiv.org/abs/1302.5445}
}

@ARTICLE{GNRS99,
  author = {Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair},
  title = {Cuts, trees and {$\ell_1$}-embeddings of graphs},
  journal = {Combinatorica},
  year = {2004},
  volume = {24},
  pages = {233--269},
  number = {2},
  note = {(Preliminary version in 40th FOCS, 1999.)},
  doi = {http://dx.doi.org/10.1007/s00493-004-0015-x}
}

@INPROCEEDINGS{GNRS99-conf,
  author = {Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair},
  title = {Cuts, trees and {$\ell_1$}-embeddings of graphs},
  booktitle = focs,
  year = {1999},
  pages = {399--408},
  publisher = {IEEE Computer Soc., Los Alamitos, CA},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFFCS.1999.814611},
  mrclass = {68R10 (05C85)},
  mrnumber = {1 917 578}
}

@INPROCEEDINGS{GuptaPal05,
  author = {Anupam Gupta and Martin P{\'a}l},
  title = {Stochastic {Steiner} Trees Without a Root},
  booktitle = icalp,
  year = {2005},
  volume = {3580},
  series = lncs,
  pages = {1051-1063},
  doi = {http://dx.doi.org/10.1007/11523468_85}
}

@ARTICLE{GPRSboost11,
  author = {Gupta, Anupam and P{\'a}l, Martin and Ravi, R. and Sinha, Amitabh},
  title = {Sampling and cost-sharing: approximation algorithms for stochastic
	optimization problems},
  journal = {SIAM J. Comput.},
  year = {2011},
  volume = {40},
  pages = {1361--1401},
  number = {5},
  coden = {SMJCAT},
  doi = {http://dx.doi.org/10.1137/080732250},
  fjournal = {SIAM Journal on Computing},
  issn = {0097-5397},
  mrclass = {68W25 (90C15 90C27)},
  mrnumber = {2854577}
}

@INPROCEEDINGS{GuptaPRSwed05,
  author = {Anupam Gupta and Martin P{\'a}l and R. Ravi and Amitabh Sinha},
  title = {What About {Wednesday}? Approximation Algorithms for Multistage Stochastic
	Optimization},
  booktitle = approx,
  year = {2005},
  volume = {3624},
  series = lncs,
  pages = {86-98},
  doi = {http://dx.doi.org/10.1007/11538462_8}
}

@INPROCEEDINGS{GPRSboost04,
  author = {Anupam Gupta and Martin P{\'a}l and R. Ravi and Amitabh Sinha},
  title = {Boosted Sampling: Approximation algorithms for stochastic optimization
	problems},
  booktitle = stoc,
  year = {2004},
  pages = {417--426},
  doi = {http://doi.acm.org/10.1145/1007352.1007419}
}

@ARTICLE{GRSfocs04,
  author = {Gupta, Anupam and Ravi, R. and Sinha, Amitabh},
  title = {{LP Rounding Approximation Algorithms for Stochastic Network Design}},
  journal = {Mathematics of Operations Research},
  year = {2007},
  volume = {32},
  pages = {345-364},
  number = {2},
  doi = {http://dx.doi.org/10.1287/moor.1060.0237}
}

@INPROCEEDINGS{GRSfocs04-proc,
  author = {Anupam Gupta and R. Ravi and Amitabh Sinha},
  title = {An Edge in Time Saves Nine: {LP} Rounding Approximation Algorithms
	for Stochastic Network Design.},
  booktitle = focs,
  year = {2004},
  pages = {218--227},
  doi = {http://dx.doi.org/10.1109/FOCS.2004.11}
}

@INPROCEEDINGS{GRST10,
  author = {Anupam Gupta and Aaron Roth and Grant Schoenebeck and Kunal Talwar},
  title = {Constrained Non-monotone Submodular Maximization: Offline and Secretary
	Algorithms},
  booktitle = {WINE},
  year = {2010},
  pages = {246-257},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://dx.doi.org/10.1007/978-3-642-17572-5_20}
}

@ARTICLE{GRST10-arxiv,
  author = {Anupam Gupta and Aaron Roth and Grant Schoenebeck and Kunal Talwar},
  title = {Constrained Non-Monotone Submodular Maximization: Offline and Secretary
	Algorithms},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1003.1517},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1003.1517}
}

@INPROCEEDINGS{GRU11-tcc,
  author = {Anupam Gupta and Aaron Roth and Jonathan Ullman},
  title = {Iterative Constructions and Private Data Release},
  booktitle = {TCC},
  year = {2012},
  pages = {339-356},
  month = {Apr},
  doi = {http://dx.doi.org/10.1007/978-3-642-28914-9_19}
}

@ARTICLE{GRU11-arxiv,
  author = {Anupam Gupta and Aaron Roth and Jonathan Ullman},
  title = {Iterative Constructions and Private Data Release},
  journal = {CoRR},
  year = {2011},
  volume = {abs/1107.3731},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/1107.3731}
}

@ARTICLE{GScovering03,
  author = {Anupam Gupta and Aravind Srinivasan},
  title = {An Improved Approximation Ratio for the {Covering} {Steiner} Problem},
  journal = {Theory of Computing},
  year = {2006},
  volume = {2},
  pages = {53--64},
  doi = {http://dx.doi.org/10.4086/toc.2006.v002a003}
}

@INPROCEEDINGS{GScovering03-conf,
  author = {Anupam Gupta and Aravind Srinivasan},
  title = {On the {Covering} {Steiner} Problem},
  booktitle = fsttcs,
  year = {2003},
  pages = {244--251},
  doi = {http://dx.doi.org/10.1007/978-3-540-24597-1_21}
}

@ARTICLE{GSTxmono04,
  author = {Anupam Gupta and Aravind Srinivasan and {\'E}va Tardos},
  title = {Cost-Sharing Mechanisms for Network Design.},
  journal = {Algorithmica},
  year = {2008},
  volume = {50},
  pages = {98--119},
  number = {1},
  doi = {http://dx.doi.org/10.1007/s00453-007-9065-y},
  fjournal = {Algorithmica. An International Journal in Computer Science}
}

@INPROCEEDINGS{GSTxmono04-proc,
  author = {Anupam Gupta and Aravind Srinivasan and {\'E}va Tardos},
  title = {Cost-Sharing Mechanisms for Network Design.},
  booktitle = approx,
  year = {2004},
  volume = {3122},
  series = lncs,
  pages = {139--150},
  doi = {http://dx.doi.org/10.1007/s00453-007-9065-y}
}

@ARTICLE{GT11,
  author = {Gupta, Anupam and Talwar, Kunal},
  title = {Making Doubling Metrics Geodesic},
  journal = {Algorithmica},
  year = {2011},
  volume = {59},
  pages = {66-80},
  number = {1},
  doi = {http://dx.doi.org/10.1007/s00453-010-9397-x}
}

@INPROCEEDINGS{GuptaT08,
  author = {Anupam Gupta and Kunal Talwar},
  title = {How to Complete a Doubling Metric},
  booktitle = latin,
  year = {2008},
  pages = {36-47},
  doi = {http://dx.doi.org/10.1007/978-3-540-78773-0_4}
}

@ARTICLE{GTalwar-convexify,
  author = {Anupam Gupta and Kunal Talwar},
  title = {How to Complete a Doubling Metric},
  journal = {CoRR},
  year = {2007},
  volume = {abs/0712.3331},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/0712.3331}
}

@INPROCEEDINGS{GT06,
  author = {Anupam Gupta and Kunal Talwar},
  title = {Approximating unique games},
  booktitle = soda,
  year = {2006},
  pages = {99-106},
  doi = {http://doi.acm.org/10.1145/1109557.1109569}
}

@INPROCEEDINGS{GTW13-spcut,
  author = {Anupam Gupta and Kunal Talwar and David Witmer},
  title = {On the Non-Uniform Sparsest Cut Problem on Bounded Treewidth Graphs},
  booktitle = stoc,
  year = {2013},
  month = {Jun},
}

@ARTICLE{GT-arxiv,
  author = {Anupam Gupta and Kanat Tangwongsan},
  title = {Simpler Analyses of Local Search Algorithms for Facility Location},
  journal = {CoRR},
  year = {2008},
  volume = {abs/0809.2554},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url = {http://arxiv.org/abs/0809.2554}
}

@INPROCEEDINGS{GT00,
  author = {Anupam Gupta and {\'E}va Tardos},
  title = {A Constant Factor Approximation Algorithm for a Class of Classification
	Problems},
  booktitle = stoc,
  year = {2000},
  pages = {652--658},
  doi = {http://doi.acm.org/10.1145/335305.335397}
}

@INPROCEEDINGS{GuptaZane03,
  author = {Anupam Gupta and Francis X. Zane},
  title = {Counting Inversions in Lists},
  booktitle = soda,
  year = {2003},
  pages = {253--254},
  doi = {http://doi.acm.org/10.1145/644108.644150}
}

@ARTICLE{KrauseGGK11,
  author = {Andreas Krause and Carlos Guestrin and Anupam Gupta and Jon M. Kleinberg},
  title = {Robust sensor placements at informative and communication-efficient
	locations},
  journal = {ACM Transactions on Sensor Networks},
  year = {2011},
  volume = {7},
  pages = {31},
  number = {4},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1921621.1921625}
}

@INPROCEEDINGS{KrauseGGK06,
  author = {Andreas Krause and Carlos Guestrin and Anupam Gupta and Jon M. Kleinberg},
  title = {Near-optimal sensor placements: maximizing information while minimizing
	communication cost},
  booktitle = {Conference on Information Processing in Sensor Networks},
  year = {2006},
  pages = {2-10},
  doi = {http://doi.acm.org/10.1145/1127777.1127782}
}

@INPROCEEDINGS{KMGG-nips,
  author = {Andreas Krause and Brendan McMahan and Carlos Guestrin and Anupam
	Gupta},
  title = {Selecting Observations against Adversarial Objectives},
  booktitle = {Advances in Neural Information Processing Systems 20},
  year = {2008},
  editor = {J.C. Platt and D. Koller and Y. Singer and S. Roweis},
  pages = {777--784},
  address = {Cambridge, MA},
  publisher = {MIT Press},
  file = {:http\://books.nips.cc/papers/files/nips20/NIPS2007_0205.pdf:URL},
  url = {http://books.nips.cc/nips20.html}
}

@ARTICLE{KrauseGGK06-jmlr,
  author = {Andreas Krause and Brendan McMahan and Carlos Guestrin and Anupam
	Gupta},
  title = {Robust Submodular Observation Selection},
  journal = {Journal of Machine Learning Research},
  year = {2008},
  volume = {9},
  pages = {2761--2801},
  month = {December},
  url = {http://jmlr.csail.mit.edu/papers/v9/krause08b.html}
}

@ARTICLE{KrauseRGG09-tac,
  author = {Andreas Krause and Ram Rajagopal and Anupam Gupta and Carlos Guestrin},
  title = {Simultaneous Optimization of Sensor Placements and Balanced Schedules},
  journal = {IEEE Transactions on Automatic Control},
  year = {2011},
  volume = {56},
  pages = {2390-2405},
  number = {10},
  doi = {http://dx.doi.org/10.1109/TAC.2011.2164010}
}

@INPROCEEDINGS{KrauseRGG09,
  author = {Andreas Krause and Ram Rajagopal and Anupam Gupta and Carlos Guestrin},
  title = {Simultaneous placement and scheduling of sensors},
  booktitle = {IPSN},
  year = {2009},
  pages = {181-192},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  doi = {http://doi.acm.org/10.1145/1602165.1602183}
}

@INPROCEEDINGS{KGR02,
  author = {Amit Kumar and Anupam Gupta and Tim Roughgarden},
  title = {A Constant-Factor Approximation Algorithm for the Multicommodity
	Rent-or-Buy Problem},
  booktitle = focs,
  year = {2002},
  pages = {333--342},
  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181956}
}

@ARTICLE{LXGGLW10-jmlr,
  author = {Han Liu and Min Xu and Haijie Gu and Anupam Gupta and John Lafferty
	and Larry Wasserman},
  title = {Forest Density Estimation},
  journal = {Journal of Machine Learning Research},
  year = {2011},
  volume = {12},
  pages = {907--951},
  month = {March},
  url = {http://jmlr.csail.mit.edu/papers/v12/liu11a.html}
}

@ARTICLE{LXGGLW10-arxiv,
  author = {Han Liu and Min Xu and Haijie Gu and Anupam Gupta and John Lafferty
	and Larry Wasserman},
  title = {Forest Density Estimation},
  journal = {CoRR},
  year = {2010},
  volume = {abs/1001.1557},
  ee = {http://arxiv.org/abs/1001.1557},
  url = {http://arxiv.org/abs/1001.1557}
}

@INPROCEEDINGS{SGRZ10,
  author = {Vyas Sekar and Anupam Gupta and Michael K. Reiter and Hui Zhang},
  title = {Coordinated Sampling sans Origin-Destination Identifiers: Algorithms,
	Analysis, and Evaluation},
  booktitle = {IEEE Communication Systems and Networks (COMSNETS)},
  year = {2010},
  pages = {1--10},
  doi = {http://dx.doi.org/10.1109/COMSNETS.2010.5432011}
}

@INPROCEEDINGS{SKGR10,
  author = {Vyas Sekar and Ravishankar Krishnaswamy and Anupam Gupta and Michael
	K. Reiter},
  title = {Network-Wide Deployment of Intrusion Detection and Prevention Systems},
  booktitle = {ACM CoNEXT},
  year = {2010},
  doi = {http://doi.acm.org/10.1145/1921168.1921192},
  url = {http://conferences.sigcomm.org/co-next/2010/CoNEXT_papers/18-Sekar.pdf}
}