%--------------------------------------------------------------------------------%
% List of resources on
% "Approximation and Online Algorithms: Facility Location Problems".
%
% Author: Mário César San Felice.
% Email: [my last name] (at) ic.unicamp.br
%
% Last modification in 29/10/2014
%--------------------------------------------------------------------------------%

%--------------------------------------------------------------------------------%
% Books
%--------------------------------------------------------------------------------%

@Book{BE98,
 author = {A. Borodin and R. El-Yaniv},
 title = {Online Computation and Competitive {A}nalysis},
 publisher = {Press Syndicate of the University of Cambridge},
 year = {1998},
}

@Book{Carvalhoetal01,
 author = {M.H. Carvalho and M.R. Cerioli and R. Dahab and P. Feofiloff and C.G. Fernandes and C.E. Ferreira and K.S. Guimaraes and F.K. Miyazawa and J.C. Pina Jr. and J. Soares and Y. Wakabayashi},
 title = {Uma Introdução Sucinta a Algoritmos de Aproximação},
 publisher = {Editora do IMPA, Rio de Janeiro},
 year = {2001},
}

@Book{Va03,
 author = {Vazirani, Vijay V.},
 title = {Approximation {A}lgorithms},
 publisher = {Springer},
 year = {2003},
}

@Book{MU05,
 author = {M. Mitzenmacher and E. Upfal},
 title = {Probability and Computing - Randomized Algorithms and Probabilistic Analysis},
 publisher = {Cambridge},
 year = {2005},
}

@article{BN09a,
 author = {N. Buchbinder and J. (Seffi) Naor},
 title = {The Design of Competitive Online Algorithms via a Primal-Dual Approach},
 journal = {Foundations and Trends in Theoretical Computer Science},
 volume = {3},
 pages = {93--263},
 year = {2009},
}

@Book{WS11,
 author = {D.P. Williamson and D.B. Shmoys},
 title = {The Design of Approximation Algorithms},
 publisher = {Cambridge University Press},
 year = {2011},
}

%--------------------------------------------------------------------------------%
% Approximation Papers
%--------------------------------------------------------------------------------%

@Article{St63,
 author = {Stollsteimer, John F.},
 title = {A Working Model for Plant Numbers and Locations},
 journal = {Farm Econom.},
 year = {1963},
 volume = {45},
 pages = {631--645},
}

@Article{KH63,
 author = {A.A. Kuehn and M.J. Hamburger},
 title = {A Heuristic Program for Locating Warehouses},
 journal = {Management Sci.},
 year = {1963},
 volume = {9},
 pages = {643--666},
}

@Article{Ma64,
 author = {A.S. Manne},
 title = {Plant Location Under Economies-of-Scale-Decentralization and Computation},
 journal = {Management Sci.},
 year = {1964},
 volume = {11},
 pages = {213--235},
}

@Inproceedings{Ba66,
 author = {M.L. Balinksi},
 title = {On Finding Integer Solutions to Linear Programs},
 booktitle = {IBM Scientific Computing Symposium on Combinatorial Problems},
 year = {1966},
 pages = {225--248},
}

@Article{Ho82,
 author = {D.S. Hochbaum},
 title = {Heuristics for the Fixed Cost Median Problem},
 journal = {Math Programming},
 year = {1982},
 volume = {22},
 pages = {148--162},
}

@Inproceedings{CNW90,
 author = {G. Cornuéjols and G. Nemhauser and L. Wolsey},
 title = {The Uncapacitated Facility Location Problem},
 booktitle = {Discrete Location Theory},
 year = {1990},
 pages = {119--171},
}

@Inproceedings{LV92a,
 author = {J.H. Lin and J.S. Vitter},
 title = {$epsilon$-Approximation with Minimum Packing Constraint Violation},
 booktitle = {Theory of Computing, 24th Annual ACM Symposium, STOC 1992},
 year = {1992},
 pages = {771--782},
}

@Article{LV92b,
 author = {J.H. Lin and J.S. Vitter},
 title = {Approximation Algorithms for Geometric Median Problems},
 journal = {Inform. Proc. Lett.},
 year = {1992},
 volume = {44},
 pages = {245--249},
}

@article{GW92,
 author = {M. Goemans and D.P. Williamson},
 title = {A General Approximation Technique For Constrained Forest Problems},
 journal = {SIAM Journal on Computing},
 year = {1992},
 volume = {24},
 pages = {296--317},
}

@article{WGMV95,
 author={D.P. Williamson and M.X. Goemans and M. Mihail and V.V. Vazirani},
 title={A primal-dual approximation algorithm for generalized {S}teiner network problems},
 year={1995},
 issn={0209-9683},
 journal={Combinatorica},
 volume={15},
 number={3},
 doi={10.1007/BF01299747},
 url={http://dx.doi.org/10.1007/BF01299747},
 publisher={Springer-Verlag},
 keywords={05 C 40; 68 Q 25; 90 C 10; 90 C 35},
 pages={435-454},
 language={English},
}

@Inproceedings{STA97,
 author = {D.B. Shmoys and E. Tardos and K. Aardal},
 title = {Approximation Algorithms for Facility Location Problems},
 booktitle = {Theory of Computing, 29th Annual ACM Symposium, STOC 1997},
 year = {1997},
 pages = {265--274},
}

@Inproceedings{GK98,
 author = {S. Guha and S. Khuller},
 title = {Greedy Strikes Back: Improved Facility Location Algorithms},
 booktitle = {Journal of Algorithms},
 year = {1998},
 pages = {649--657},
}

@Inproceedings{Ch98,
 author = {Chudak, Fabián A.},
 title = {Improved Approximation Algorithms for Uncapacitated Facility Location},
 booktitle = {Integer Programming and Combinatorial Optimization},
 year = {1998},
 pages = {180--194},
 publisher = {Springer},
}

@Inproceedings{KPR98,
 author = {M.R. Korupolu and C.G. Plaxton and R. Rajaraman},
 title = {Analysis of a Local Search Heuristic for Facility Location Problems},
 booktitle = {Discrete Algorithms, 9th Annual ACM-SIAM Symposium, SODA 1998},
 year = {1998},
 pages = {1--10},
}

@Inproceedings{CGTS99,
 author = {M. Charikar and S. Guha and E. Tardos and D.B. Shmoys},
 title = {A Constant-Factor Approximation Algorithm for the $k$-Median P},
 booktitle = {Theory of Computing, 31th Annual ACM Symposium, STOC 1999},
 year = {1999},
 pages = {1--10},
 publisher = {ACM},
}

@Inproceedings{CS99,
 author = {F.A. Chudak and D.B. Shmoys},
 title = {Improved Approximation Algorithms for a Capacitated Facility Location Problem},
 booktitle = {Discrete Algorithms, 10th Annual ACM-SIAM Symposium, SODA 1999},
 year = {1999},
 pages = {875--876},
 publisher = {Society for Industrial and Applied Mathematics},
}

@Inproceedings{JV99,
 author = {K. Jain and V.V. Vazirani},
 title = {Primal-Dual Approximation Algorithms for Metric Facility Location and $k$-Median Problems},
 booktitle = {Journal of the ACM},
 year = {1999},
 pages = {2--13},
}

@Inproceedings{CG99,
 author = {M. Charikar and S. Guha},
 title = {Improved Combinatorial Algorithms for the Facility Location and $k$-Median Problems},
 booktitle = {Foundations of Computer Science, 40th Annual IEEE Symposium, FOCS 1999},
 year = {1999},
 pages = {378--388},
 publisher = {IEEE Computer Society},
}

@inproceedings{Sh00,
 author = {Shmoys, David B.},
 title = {Approximation Algorithms for Facility Location Problems},
 booktitle = {Approximation Algorithms for Combinatorial Optimization, 3rd International Workshop, APPROX 2000},
 series = {Lecture Notes in Computer Science},
 number = {1913},
 year = {2000},
 isbn = {3-540-67996-0},
 pages = {27--33},
 numpages = {7},
 url = {http://dl.acm.org/citation.cfm?id=646688.703104},
 acmid = {703104},
 publisher = {Springer-Verlag},
 address = {Berlin, Germany},
}

@Inproceedings{AGKMMP01,
 author = {V. Arya and N. Garg and R. Khandekar and A. Meyerson and K. Munagala and V. Pandit},
 title = {Local Search Heuristic for $k$-Median and Facility Location Problems},
 booktitle = {Theory of Computing, 33rd Annual ACM Symposium, STOC 2001},
 year = {2001},
 pages = {21--29},
 publisher = {ACM},
}

@Article{JV01,
 author = {K. Jain and V.V. Vazirani},
 title = {Approximation Algorithms for Metric Facility Location and $k$-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation},
 journal = {Journal of the ACM},
 year = {2001},
 volume = {48},
 number = {2},
 pages = {274--296},
}

@Inproceedings{PTW01,
 author = {M. Pal and E. Tardos and T. Wexler},
 title = {Facility Location with Nonuniform Hard Capacities},
 booktitle = {Foundations of Computer Science, 42nd IEEE Symposium, FOCS 2001},
 year = {2001},
 pages = {329--338},
 publisher = {IEEE Computer Society},
}

@article{Ja01,
 author = {Jain, Kamal},
 title = {A Factor 2 Approximation Algorithm for the Generalized {S}teiner Network Problem},
 year = {2001},
 issn = {0209-9683},
 journal = {Combinatorica},
 volume = {21},
 number = {1},
 doi = {10.1007/s004930170004},
 url = {http://dx.doi.org/10.1007/s004930170004},
 publisher = {Bolyai Society – Springer-Verlag},
 keywords = {AMS Subject Classification (2000) Classes:  68W25, 90C57},
 pages = {39-60},
 language = {English},
}

@inproceedings{CKMN01,
 author = {M. Charikar and S. Khuller and D.M. Mount and G. Narasimhan},
 title = {Algorithms for Facility Location Problems with Outliers},
 booktitle = {Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '01},
 year = {2001},
 isbn = {0-89871-490-7},
 location = {Washington, D.C., USA},
 pages = {642--651},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=365411.365555},
 acmid = {365555},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
}

@Inproceedings{JMS02,
 author = {K. Jain and M. Mahdian and A. Saberi},
 title = {A New Greedy Approach for Facility Location Problems},
 booktitle = {Theory of Computing, 34th Annual ACM Symposium, STOC 2002},
 year = {2002},
 pages = {731--740}
}

@inproceedings{MYZ02,
 author = {M. Mahdian and Y. Ye and J. Zhang},
 title = {Improved Approximation Algorithms for Metric Facility Location Problems},
 booktitle = {Approximation Algorithms for Combinatorial Optimization, 5th International Workshop, APPROX 2002},
 series = {Lecture Notes in Computer Science},
 number = {2462},
 year = {2002},
 isbn = {3-540-44186-7},
 pages = {229--242},
 numpages = {14},
 url = {http://dl.acm.org/citation.cfm?id=646689.703120},
 acmid = {703120},
 publisher = {Springer-Verlag},
 address = {London, UK, UK},
}

@Inproceedings{MYZ03,
 author = {M. Mahdian and Y. Ye and J. Zhang},
 title = {A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem},
 booktitle = {Approximation Algorithms for Combinatorial Optimization, 6th International Workshop, APPROX 2003},
 series = {Lecture Notes in Computer Science},
 number = {2764},
 year = {2003},
 pages = {129--140},
}

@article{MYZ06,
 author = {M. Mahdian and Y. Ye and J. Zhang},
 title = {Approximation Algorithms for Metric Facility Location Problems},
 journal = {SIAM Journal on Computing},
 volume = {36},
 pages = {411--432},
 year = {2006},
}

@Article{CS04,
 author = {F.A. Chudak and D.B. Shmoys},
 title = {Improved Approximation Algorithms for the Uncapacitated Facility Location Problem},
 journal = {SIAM J. Comput.},
 year = {2004},
 pages = {1--25},
 publisher = {Society for Industrial and Applied Mathematics},
}

@Article{CW05,
 author = {F.A. Chudak and D.P. Williamson},
 title = {Improved Approximation Algorithms for Capacitated Facility Location Problems},
 journal = {Math. Program.},
 volume = {102},
 number = {2},
 year = {2005},
 pages = {207--222},
 publisher = {Springer-Verlag New York, Inc.},
}

@inproceedings{ST06,
 author = {Z. Svitkina and E. Tardos},
 title = {Facility Location with Hierarchical Facility Costs},
 booktitle = {Discrete Algorithms, 17th Annual ACM-SIAM Symposium, SODA 2006},
 year = {2006},
 pages = {153--161},
 publisher = {ACM},
}

@inproceedings{By07,
 author = {Byrka, Jaroslaw},
 title = {An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem},
 booktitle = {10th International Workshop on Approximation and 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2007},
 series = {Lecture Notes in Computer Science},
 number = {4627},
 year = {2007},
 isbn = {978-3-540-74207-4},
 location = {Princeton, NJ, USA},
 pages = {29--43},
 numpages = {15},
 url = {http://dx.doi.org/10.1007/978-3-540-74208-1_3},
 doi = {10.1007/978-3-540-74208-1_3},
 acmid = {1459741},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
}

@article{ByA10,
 author = {J. Byrka and K. Aardal},
 title = {An Optimal Bifactor Approximation Algorithm for the Metric Facility Location Problem},
 journal = {SIAM Journal on Computing},
 volume = {39},
 pages = {2212--2231},
 year = {2010},
}

@inproceedings{CN07,
 author = {F. Chudak and K. Nagano},
 title = {Efficient Solutions to Relaxations of Combinatorial Problems with Submodular Penalties via the {L}ovász Extension and Non-Smooth Convex Optimization},
 booktitle = {Discrete Algorithms, 18th Annual ACM-SIAM Symposium, SODA 2007},
 year = {2007},
 pages = {79--88},
 publisher = {Society for Industrial and Applied Mathematics},
}

@inproceedings{DHMSOZ07,
 author = {E.D. Demaine and M. Hajiaghayi and H. Mahini and A.S. Sayedi-Roshkhar and S. Oveisgharan and M. Zadimoghaddam},
 title = {Minimizing Movement},
 booktitle = {Discrete Algorithms, 18th Annual ACM-SIAM Symposium, SODA 2007},
 year = {2007},
 pages = {258--267},
 publisher = {Society for Industrial and Applied Mathematics},
}

@inproceedings{FS08,
 author = {Z. Friggstad and M.R. Salavatipour},
 title = {Minimizing Movement in Mobile Facility Location Problems},
 booktitle = {Foundations of Computer Science, 49th Annual IEEE Symposium, FOCS 2008},
 year = {2008},
 pages = {357--366},
 publisher = {IEEE Computer Society},
}

@article{XX09,
 author={G. Xu and J. Xu},
 title={An improved approximation algorithm for uncapacitated facility location problem with penalties},
 journal={Journal of Combinatorial Optimization},
 volume={17},
 number={4},
 pages={424-436},
 year={2009},
 issn={1382-6905},
 doi={10.1007/s10878-007-9127-8},
 url={http://dx.doi.org/10.1007/s10878-007-9127-8},
 publisher={Springer US},
 keywords={Algorithms; Approximation algorithms; Facility location problem; Outliers},
 language={English},
}

@inproceedings{ABS10,
 author = {P. Awasthi and A. Blum and O. Sheffet},
 title = {Stability Yields a PTAS for k-Median and k-Means Clustering},
 booktitle = {Foundations of Computer Science, 51st Annual IEEE Symposium, FOCS 2010},
 year = {2010},
 pages = {309--318},
 publisher = {IEEE Computer Society},
}

@inproceedings{Li11,
 author = {Li, Shi},
 title = {A 1.488 approximation algorithm for the uncapacitated facility location problem},
 booktitle = {Automata, Languages and Programming, 38th International Conference, ICALP 2011},
 series = {Lecture Notes in Computer Science},
 number = {6756},
 year = {2011},
 isbn = {978-3-642-22011-1},
 location = {Zurich, Switzerland},
 pages = {77--88},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=2027223.2027230},
 acmid = {2027230},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {approximation, facility location problem, theory},
}

@article{Li13,
 author = {Li, Shi},
 title = {A 1.488 approximation algorithm for the uncapacitated facility location problem},
 journal = {Information and Computation},
 volume = {222},
 pages = {45--58},
 year = {2013},
}

%--------------------------------------------------------------------------------%
% Online and Incremental Papers
%--------------------------------------------------------------------------------%

@Inproceedings{MP00,
 author = {R.R. Mettu and C.G. Plaxton},
 title = {The Online Median Problem},
 booktitle = {Foundations of Computer Science, 41st Annual IEEE Symposium, FOCS 2000},
 year = {2000},
 pages = {339--348},
 publisher = {IEEE Computer Society},
}

@inproceedings{Me01,
 author = {Meyerson, Adam},
 title = {Online Facility Location},
 booktitle = {Foundations of Computer Science, 42nd IEEE Symposium, FOCS 2001},
 year = {2001},
 isbn = {0-7695-1390-5},
 pages = {426--431},
 url = {http://dl.acm.org/citation.cfm?id=874063.875567},
 acmid = {875567},
}

@inproceedings{Fo03,
 author = {Fotakis, Dimitris},
 title = {On the Competitive Ratio for Online Facility Location},
 booktitle = {Automata, Languages and Programming, 30th International Conference, ICALP 2003},
 series = {Lecture Notes in Computer Science},
 number = {2719},
 year = {2003},
 isbn = {3-540-40493-7},
 location = {Eindhoven, The Netherlands},
 pages = {637--652},
 numpages = {16},
 url = {http://dl.acm.org/citation.cfm?id=1759210.1759273},
 acmid = {1759273},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
}

@article{Fo08,
 author = {Fotakis, Dimitris},
 title = {On the Competitive Ratio for Online Facility Location},
 journal = {Algorithmica},
 volume = {50},
 pages = {1--57},
 year = {2008},
}

@inproceedings{AAA03,
 author = {N. Alon and B. Awerbuch and Y. Azar and N. Buchbinder and J. (Seffi) Naor},
 title = {The Online Set Cover Problem},
 booktitle = {Theory of Computing, 35th Annual ACM Symposium, STOC 2003},
 year = {2003},
 pages = {100--105},
 publisher = {ACM},
}

@Article{ABUH04,
 author = {A. Anagnostopoulos and R. Bent and E. Upfal and P.V. Hentenryck},
 title = {A Simple and Deterministic Competitive Algorithm for Online Facility Location},
 year = {2004},
 journal = {Inf. Comput.},
 volume = {194},
 number = {2},
 pages = {175--202},
 publisher = {Academic Press, Inc.},
}

@inproceedings{Fo04,
 author = {Fotakis, Dimitris},
 title = {Incremental Algorithms for Facility Location and $k$-Median},
 booktitle = {Algorithms, 12th Annual European Symposium, ESA 2004},
 series = {Lecture Notes in Computer Science},
 number = {3221},
 year = {2004},
 pages = {347--358},
 publisher = {Springer},
}

@article{DL05,
 author = {R. Dorrigiv and A. López-Ortiz},
 title = {A Survey of Performance Measures for On-line Algorithms},
 journal = {SIGACT News},
 month = {September},
 year = {2005},
 pages = {67--81},
 publisher = {ACM},
}

@inproceedings{Me05,
 author = {Meyerson, Adam},
 title = {The Parking Permit Problem},
 booktitle = {Foundations of Computer Science, 46th Annual IEEE Symposium, FOCS 2005},
 year = {2005},
 pages = {274--284},
 publisher = {IEEE Computer Society},
}

@incollection {Fo06,
 author = {Fotakis, Dimitris},
 title = {Memoryless Facility Location in One Pass},
 booktitle = {Theoretical Aspects of Computer Science, 23rd International Symposium, STACS 2006},
 publisher = {Springer Berlin / Heidelberg},
 pages = {608-620},
 year = {2006}
}

@article{Fo07,
 author = {Fotakis, Dimitris},
 title = {A Primal-Dual Algorithm for Online Non-Uniform Facility Location},
 journal = {Journal of Discrete Algorithms},
 volume = {5},
 number = {1},
 year = {2007},
 issn = {1570-8667},
 pages = {141--148},
 numpages = {8},
 url = {http://dx.doi.org/10.1016/j.jda.2006.03.001},
 doi = {10.1016/j.jda.2006.03.001},
 acmid = {1224672},
 publisher = {Elsevier Science Publishers B. V.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 keywords = {Competitive analysis, Metric facility location, Online algorithms},
}

@inproceedings{NW08,
 author = {C. Nagarajan and D.P. Williamson},
 title = {Offline and Online Facility Leasing},
 booktitle = {Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008},
 series = {Lecture Notes in Computer Science},
 number = {5035},
 year = {2008},
 isbn = {3-540-68886-2, 978-3-540-68886-0},
 location = {Bertinoro, Italy},
 pages = {303--315},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=1788814.1788842},
 acmid = {1788842},
 publisher = {Springer-Verlag},
 address = {Berlin, Germany},
}

@inproceedings{AL08,
 author = {S. Albers and S. Lauer},
 title = {On List Update with Locality of Reference},
 booktitle = {Automata, Languages and Programming, 35th International Colloquium, ICALP 2008},
 year = {2008},
 pages = {96--107},
 publisher = {Springer-Verlag},
}

@Article{BN09b,
 author = {N. Buchbinder and J. (Seffi) Naor},
 title = {Online Primal-Dual Algorithms for Covering and Packing},
 journal = {Math. Oper. Res.},
 volume = {34},
 year = {2009},
 pages = {270--286},
}

@inproceedings{AS09,
 author = {S. Angelopoulos and P. Schweitzer},
 title = {Paging and List Update Under Bijective Analysis},
 booktitle = {Discrete Algorithms, 20th Annual ACM-SIAM Symposium, SODA 2009},
 year = {2009},
 pages = {1136--1145},
 publisher = {Society for Industrial and Applied Mathematics},
}

@inproceedings{GKR09,
 author = {A. Gupta and R. Krishnaswamy and R. Ravi},
 title = {Online and Stochastic Survivable Network Design},
 booktitle = {Theory of Computing, 41st Annual ACM Symposium, STOC 2009},
 year = {2009},
 pages = {685--694},
 publisher = {ACM},
}

@article {DI11,
 author = {G. Divéki and C. Imreh},
 title = {Online Facility Location with Facility Movements},
 journal = {Central European Journal of Operations Research},
 publisher = {Physica Verlag, An Imprint of Springer-Verlag GmbH},
 pages = {191-200},
 year = {2011}
}

@article{Fo11,
 author = {Fotakis, Dimitris},
 title = {Online and Incremental Algorithms for Facility Location},
 journal = {SIGACT News},
 issue_date = {March 2011},
 volume = {42},
 number = {1},
 month = mar,
 year = {2011},
 issn = {0163-5700},
 pages = {97--131},
 numpages = {35},
 url = {http://doi.acm.org/10.1145/1959045.1959065},
 doi = {10.1145/1959045.1959065},
 acmid = {1959065},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@article{NW13,
 author = {C. Nagarajan and D.P. Williamson},
 title = {Offline and online facility leasing},
 journal = {Discrete Optimization},
 volume = {10},
 number = {4},
 pages = {361--370},
 year = {2013},
 issn = {1572-5286},
 doi = {http://dx.doi.org/10.1016/j.disopt.2013.10.001},
 url = {http://www.sciencedirect.com/science/article/pii/S1572528613000509},
 keywords = {Online algorithm},
 keywords = {Facility location},
 keywords = {Parking permit problem},
 keywords = {Facility leasing},
}

%--------------------------------------------------------------------------------%
% Connected Facility Location Papers
%--------------------------------------------------------------------------------%

@article{RSL77,
 author={D.J. Rosenkrantz and R.E. Stearns and P.M. Lewis},
 title={An Analysis of Several Heuristics for the Traveling Salesman Problem},
 volume={6},
 number={3},
 journal={SIAM Journal on Computing},
 publisher={Academic Press},
 pages={563--581}
 year={1977},
}

@article{IW91,
 author = {M. Imase and B.M. Waxman},
 title = {Dynamic {S}teiner Tree Problem},
 volume = {4},
 number = {3},
 journal = {SIAM Journal on Discrete Mathematics},
 pages = {369--384},
 year = {1991},
}

@inproceedings{AAB96,
 author = {B. Awerbuch and Y. Azar and Y. Bartal},
 title = {On-line generalized {S}teiner problem},
 booktitle = {Discrete Algorithms, 7th Annual ACM-SIAM Symposium, SODA 1996},
 isbn = {0-89871-366-8},
 location = {Atlanta, Georgia, USA},
 pages = {68--74},
 numpages = {7},
 url = {http://dl.acm.org/citation.cfm?id=313852.313888},
 acmid = {313888},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 year = {1996},
}

@inproceedings{BC97,
 author = {P. Berman and C. Coulston},
 title = {On-line algorithms for {S}teiner tree problems (extended abstract)},
 booktitle = {Theory of Computing, 29th Annual ACM Symposium, STOC 1997},
 isbn = {0-89791-888-6},
 location = {El Paso, Texas, USA},
 pages = {344--353},
 numpages = {10},
 url = {http://doi.acm.org/10.1145/258533.258618},
 doi = {10.1145/258533.258618},
 acmid = {258618},
 publisher = {ACM},
 address = {New York, NY, USA},
 year = {1997},
}

@article{KZ02,
 author = {S. Khuller and A. Zhu},
 title = {The General {S}teiner Tree-Star Problem},
 journal = {Inf. Process. Lett.},
 issue_date = {30 November 2002},
 volume = {84},
 number = {4},
 issn = {0020-0190},
 pages = {215--220},
 numpages = {6},
 url = {http://dx.doi.org/10.1016/S0020-0190(02)00271-5},
 doi = {10.1016/S0020-0190(02)00271-5},
 acmid = {603550},
 publisher = {Elsevier North-Holland, Inc.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 keywords = {{S}teiner trees, approximation algorithms, facility location},
 month = nov,
 year = {2002},
}

@inproceedings{GKR03,
 author = {A. Gupta and A. Kumar and T. Roughgarden},
 title = {Simpler and Better Approximation Algorithms for Network Design},
 booktitle = {Theory of Computing, 35th Annual ACM Symposium, STOC 2003},
 isbn = {1-58113-674-9},
 location = {San Diego, CA, USA},
 pages = {365--372},
 numpages = {8},
 url = {http://doi.acm.org/10.1145/780542.780597},
 doi = {10.1145/780542.780597},
 acmid = {780597},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {approximation algorithms, network design, randomized algorithms},
 year = {2003},
}

@inproceedings{GST04,
 author = {A. Gupta and A. Srinivasan and E. Tardos},
 title = {Cost-Sharing Mechanisms for Network Design},
 booktitle = {7th International Workshop on Approximation and 8th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2004},
 series = {Lecture Notes in Computer Science},
 number = {3122},
 year = {2004},
 isbn = {978-3-540-22894-3},
 location = {Cambridge, MA, USA},
 pages = {139--150},
 numpages = {12},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
}

@article{GST08,
 author = {A. Gupta and A. Srinivasan and E. Tardos},
 title = {Cost-Sharing Mechanisms for Network Design},
 journal = {Algorithmica},
 volume = {50},
 pages = {98--119},
 year = {2008},
 }

@article{SK04,
 author={C. Swamy and A. Kumar},
 title={Primal-Dual Algorithms for Connected Facility Location Problems},
 volume={40},
 number={4},
 journal={Algorithmica},
 publisher={Springer Netherlands},
 pages={245--269},
 year={2004},
}

@article{AAB04,
 author = {B. Awerbuch and Y. Azar and Y. Bartal},
 title = {On-line generalized {S}teiner problem},
 journal = {Theoretical Computer Science},
 volume = {324},
 number = {2 - 3},
 pages = {313 - 324},
 year = {2004},
 note = {Online Algorithms: In Memoriam, Steve Seiden},
 issn = {0304-3975},
 doi = {http://dx.doi.org/10.1016/j.tcs.2004.05.021},
 url = {http://www.sciencedirect.com/science/article/pii/S0304397504003846},
 keywords = {Online},
 keywords = {Competitive},
 keywords = {Steiner tree},
 keywords = {Steiner forest}
}

@article{GKPR07,
 author={A. Gupta and A. Kumar and M. Pál and T. Roughgarden},
 title={Approximation via cost sharing: Simpler and better approximation algorithms for network design},
 volume={54},
 url={http://portal.acm.org/citation.cfm?doid=1236457.1236458},
 number={3},
 journal={Journal of the ACM},
 publisher={ACM},
 year={2007},
 note = {Article 11},
}

@inproceedings{HJC07,
 author = {M.K. Hasan and H. Jung and K.Y. Chwa},
 title = {Improved Approximation Algorithm for Connected Facility Location Problems},
 booktitle = {Combinatorial Optimization and Applications, 1st International Conference, COCOA 2007},
 series = {Lecture Notes in Computer Science},
 number = {4616},
 year = {2007},
 isbn = {3-540-73555-0, 978-3-540-73555-7},
 location = {Xi'an, China},
 pages = {311--322},
 numpages = {12},
 url = {http://dl.acm.org/citation.cfm?id=1779837.1779872},
 acmid = {1779872},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
}

@article{HJC08,
 author = {M.K. Hasan and H. Jung and K.Y. Chwa},
 title = {Approximation algorithms for connected facility location},
 journal = {Journal of Combinatorial Optimization},
 volume = {16},
 pages = {155--172},
 year = {2008},
}

@inproceedings{EGRS08,
 author = {F. Eisenbrand and F. Grandoni and T. Rothvo\ss and G. Sch\"{a}fer},
 title = {Approximating Connected Facility Location Problems Via Random Facility Sampling and Core Detouring},
 booktitle = {Discrete Algorithms, 19th Annual ACM-SIAM Symposium, SODA 2008},
 location = {San Francisco, California},
 pages = {1174--1183},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1347082.1347210},
 acmid = {1347210},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 year = {2008},
}

@article{JHC09,
 author = {H. Jung and M.K. Hasan and K.Y. Chwa},
 title = {A 6.55 factor primal-dual approximation algorithm for the connected facility location problem},
 journal = {Journal of Combinatorial Optimization},
 volume = {18},
 pages = {258--271},
 year = {2009},
}

@inproceedings{JHC08,
 author = {H. Jung and M.K. Hasan and K.Y. Chwa},
 title = {Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem},
 booktitle = {Combinatorial Optimization and Applications, 2nd International Conference, COCOA 2008},
 series = {Lecture Notes in Computer Science},
 number = {5165},
 year = {2008},
 isbn = {978-3-540-85096-0},
 location = {St. John's, Canada},
 pages = {265--277},
 numpages = {13},
 url = {http://dx.doi.org/10.1007/978-3-540-85097-7_25},
 doi = {10.1007/978-3-540-85097-7_25},
 acmid = {1429545},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 keywords = {Approximation algorithms, Facility location problem, Primal-Dual algorithms},
}

@inproceedings{GGLS08,
 author = {N. Garg and A. Gupta and S. Leonardi and P. Sankowski},
 title = {Stochastic Analyses for Online Combinatorial Optimization Problems},
 booktitle = {Discrete Algorithms, 19th Annual ACM-SIAM Symposium, SODA 2008},
 year = {2008},
 location = {San Francisco, California},
 pages = {942--951},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=1347082.1347185},
 acmid = {1347185},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
}

@inproceedings{AGLS10,
 author = {A. Anagnostopoulos and F. Grandoni and S. Leonardi and P. Sankowski},
 title = {Online Network Design with Outliers},
 booktitle = {Automata, Languages and Programming, 37th International Colloquium Conference, ICALP 2010},
 series = {Lecture Notes in Computer Science},
 number = {6198},
 year = {2010},
 isbn = {3-642-14164-1, 978-3-642-14164-5},
 location = {Bordeaux, France},
 pages = {114--126},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=1880918.1880933},
 acmid = {1880933},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
} 

@article{EGRS10,
 author={F. Eisenbrand and F. Grandoni and T. Rothvoß and G. Schäfer},
 title={Connected Facility Location Via Random Facility Sampling and Core Detouring},
 volume={76},
 url={http://linkinghub.elsevier.com/retrieve/pii/S0022000010000152},
 number={8},
 journal={Journal of Computer and System Sciences},
 publisher={Elsevier Inc.},
 pages={709--726},
 year={2010},
}

@article{GP10,
 author={A. Goel and I. Post},
 title={One Tree Suffices: A Simultaneous {O}(1)-Approximation for Single-Sink Buy-at-Bulk},
 volume={0},
 url={http://arxiv.org/abs/1004.2291},
 number={1},
 journal={Foundations of Computer Science, 51st Annual IEEE Symposium, FOCS 2010},
 publisher={IEEE},
 pages={16},
 year={2010},
}

@inproceedings{GR11,
 author = {F. Grandoni and T. Rothvo\ss},
 title = {Approximation Algorithms for Single and Multi-Commodity Connected Facility Location},
 booktitle = {Integer Programming and Combinatoral Optimization, 15th International Conference, IPCO 2011},
 series = {Lecture Notes in Computer Science},
 number = {6655},
 isbn = {978-3-642-20806-5},
 location = {New York, NY},
 pages = {248--260},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=2018158.2018178},
 acmid = {2018178},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 year = {2011},
}

@inproceedings{SWL14,
 author = {M.C. San Felice and D.P. Williamson and O. Lee},
 title = {The Online Connected Facility Location Problem},
 booktitle = {Latin American Theoretical INformatics, 11th Symposium, LATIN 2014},
 series = {Lecture Notes in Computer Science},
 number = {8392},
 location = {Montevideo - Uruguay},
 pages = {574--585},
 numpages = {12},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg},
 year = {2014},
}

@inproceedings{Um15,
 author = {Umboh, Seeun},
 title = {Online Network Design Algorithms via Hierarchical Decompositions},
 booktitle = {Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 year = {2015},
 publisher={Society for Industrial and Applied Mathematics},
 location = {San Diego, California},
 address = {Philadelphia, PA, USA},
 note={To appear. \textit{CoRR}, abs/1410.4240}}
}

@inproceedings{HSBU14,
 author = {P. Hokama and M.C. San Felice and E.C. Bracht and F.L. Usberti},
 title = {A Heuristic Approach for the Stochastic {S}teiner Tree Problem},
 booktitle = {Proceedings of the 11th DIMACS Implementation Challenge in Collaboration with ICERM: {S}teiner Tree Problems},
 year = {2014},
}

@incollection{QW11,
 author={J. Qian, and D.P. Williamson},
 title={An {O}(logn)-Competitive Algorithm for Online Constrained Forest Problems},
 year={2011},
 isbn={978-3-642-22005-0},
 booktitle={Automata, Languages and Programming},
 volume={6755},
 series={Lecture Notes in Computer Science},
 editor={Aceto, Luca and Henzinger, Monika and Sgall, Ji},
 doi={10.1007/978-3-642-22006-7_4},
 url={http://dx.doi.org/10.1007/978-3-642-22006-7_4},
 publisher={Springer Berlin Heidelberg},
 pages={37--48},
 language={English},
}

@article{GK11,
 author = {A. Gupta and J. Könemann},
 title = {Approximation algorithms for network design: A survey},
 journal = {Surveys in Operations Research and Management Science},
 volume = {16},
 number = {1},
 pages = {3--20},
 year = {2011},
 issn = {1876-7354},
 doi = {http://dx.doi.org/10.1016/j.sorms.2010.06.001},
 url = {http://www.sciencedirect.com/science/article/pii/S1876735410000024},
}

@inproceedings{GK14,
 author = {A. Gupta and A. Kumar},
 title = {Online {S}teiner Tree with Deletions},
 booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '14},
 year = {2014},
 isbn = {978-1-611973-38-9},
 location = {Portland, Oregon},
 pages = {455--467},
 numpages = {13},
 url = {http://dl.acm.org/citation.cfm?id=2634074.2634108},
 acmid = {2634108},
 publisher = {SIAM},
}

@incollection{HLP14,
 author={M. Hajiaghayi and V. Liaghat and D. Panigrahi},
 title={Near-Optimal Online Algorithms for Prize-Collecting {S}teiner Problems},
 year={2014},
 isbn={978-3-662-43947-0},
 booktitle={Automata, Languages, and Programming},
 volume={8572},
 series={Lecture Notes in Computer Science},
 editor={Esparza, Javier and Fraigniaud, Pierre and Husfeldt, Thore and Koutsoupias, Elias},
 doi={10.1007/978-3-662-43948-7_48},
 url={http://dx.doi.org/10.1007/978-3-662-43948-7_48},
 publisher={Springer Berlin Heidelberg},
 pages={576--587},
 language={English},
}

@article{vS14,
 author = {van Stee, Rob},
 title = {SIGACT News Online Algorithms Column 24: 2014 So Far},
 journal = {SIGACT News},
 issue_date = {September 2014},
 volume = {45},
 number = {3},
 month = sep,
 year = {2014},
 issn = {0163-5700},
 pages = {105--111},
 numpages = {7},
 url = {http://doi.acm.org/10.1145/2670418.2670441},
 doi = {10.1145/2670418.2670441},
 acmid = {2670441},
 publisher = {ACM},
 address = {New York, NY, USA},
}

%%% Submetidos
@Unpublished{Mario-Lagos15,
 author = {M.C. San Felice and S. Cheung and O. Lee and D.P. Williamson},
 title = {The Online Prize-Collecting Facility Location Problem},
 note = {To appear in {\em Proceedings of the Latin-American Algorithms, Graphs and Optimization, VIII Symposium, LAGOS 2015}, special volume of Electronic Notes in Discrete Mathematics (ENDM)},
 OPTkey = 	 {},
 OPTmonth = 	 {},
 year = {2015},
 OPTannote = 	 {}
}

@Unpublished{Mario-Algorithmica14,
 author = {M.C. San Felice and D.P. Williamson and O. Lee},
 title = {A Randomized {O}(log n)-Competitive Algorithm for the Online Connected Facility Location Problem},
 note = {Submitted to special issue of {\em Latin American Theoretical INformatics, 11th Symposium, LATIN 2014}, on {\em Algorithmica}},
 OPTkey = 	 {},
 OPTmonth = 	 {},
 year = {2014},
 OPTannote = 	 {}
}

@Unpublished{SWLunpublished14,
 author = {M.C. San Felice and D.P. Williamson and O. Lee},
 title = {The Online {S}teiner Tree Star Problem},
 note = {unpublished manuscript},
 OPTkey = 	 {},
 OPTmonth = 	 {},
 year = {2014},
 OPTannote = 	 {}
}