{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T01:52:11Z","timestamp":1648864331380},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,7,7]],"date-time":"2015-07-07T00:00:00Z","timestamp":1436227200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1007\/s00453-015-0021-y","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T18:41:21Z","timestamp":1436208081000},"page":"88-109","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online Network Design with Outliers"],"prefix":"10.1007","volume":"76","author":[{"given":"Aris","family":"Anagnostopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,7]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Sankowski, P.: Online network design with outliers. In: ICALP, pp. 114\u2013126 (2010)","DOI":"10.1007\/978-3-642-14165-2_11"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prophet inequalities with limited information. In: SODA, pp. 1358\u20131377 (2014)","DOI":"10.1137\/1.9781611973402.100"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: APPROX \u201907\/RANDOM \u201907, pp. 16\u201328 (2007)","DOI":"10.1007\/978-3-540-74208-1_2"},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1399589.1399596","volume":"7","author":"M Babaioff","year":"2008","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Online auctions and generalized secretary problems. SIGecom Exch. 7(2), 1\u201311 (2008). doi: 10.1145\/1399589.1399596","journal-title":"SIGecom Exch."},{"key":"21_CR5","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA, pp. 434\u2013443 (2007)"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: STOC, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"21_CR7","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)"},{"issue":"3","key":"21_CR8","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1017\/S0021900200044351","volume":"30","author":"FT Bruce","year":"1993","unstructured":"Bruce, F.T., Ferguson, T.S.: Minimizing the expected rank with full information. J. Appl. Probab. 30(3), 616\u2013626 (1993)","journal-title":"J. Appl. Probab."},{"key":"21_CR9","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: SODA \u201901, pp. 642\u2013651 (2001)"},{"key":"21_CR10","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl. 4, 627\u2013629 (1963)"},{"issue":"4","key":"21_CR11","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(4), 485\u2013497 (2004). doi: 10.1016\/j.jcss.2004.04.011","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Fiat, A., Woeginger, G.J. (eds.): Online algorithms. Lecture Notes in Computer Science, vol. 1442. Springer, Berlin (1998). The state of the art, Papers from the Workshop on the Competitive Analysis of On-line Algorithms held in Schloss Dagstuhl, June 1996","DOI":"10.1007\/BFb0029561"},{"issue":"2","key":"21_CR13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.2307\/1402748","volume":"51","author":"P Freeman","year":"1983","unstructured":"Freeman, P.: The secretary problem and its extensions: a review. Int. Stat. Rev. 51(2), 189\u2013206 (1983)","journal-title":"Int. Stat. Rev."},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the $$k$$ k -MST problem in graphs. In: STOC, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"21_CR15","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: SODA, pp. 942\u2013951 (2008)"},{"issue":"313","key":"21_CR16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/2283044","volume":"61","author":"JP Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61(313), 35\u201373 (1966). doi: 10.2307\/2283044","journal-title":"J. Am. Stat. Assoc."},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Parkes, D.C.: Adaptive limited-supply online auctions. In: EC, pp. 71\u201380 (2004)","DOI":"10.1145\/988772.988784"},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1090\/conm\/125\/1160620","volume":"125","author":"TP Hill","year":"1992","unstructured":"Hill, T.P., Kertz, R.P.: A survey of prophet inequalities in optimal stopping theory. Contemp. Math. 125, 191\u2013207 (1992)","journal-title":"Contemp. Math."},{"issue":"3","key":"21_CR19","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discret. Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"21_CR20","volume-title":"Approximation Algorithms for NP Hard Problems","author":"S Irani","year":"1996","unstructured":"Irani, S., Karlin, A.R.: On online computation. In: Hochbaum, D. (ed.) Approximation Algorithms for NP Hard Problems. PWS publishing Co., Boston (1996)"},{"issue":"3","key":"21_CR21","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539794268042","volume":"30","author":"AR Karlin","year":"2000","unstructured":"Karlin, A.R., Phillips, S.J., Raghavan, P.: Markov paging. SIAM J. Comput. 30(3), 906\u2013922 (2000)","journal-title":"SIAM J. Comput."},{"key":"21_CR22","unstructured":"Karlin, S.: Stochastic models and optimal policy for selling an asset. In: Arrow, K.J., Karlin, S., Scarf, H. (eds.) Studies in Applied Probability and Management Science, pp. 148\u2013158. Stanford University Press, Stanford (1962)"},{"issue":"1","key":"21_CR23","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-4149(87)90029-9","volume":"24","author":"D Kennedy","year":"1987","unstructured":"Kennedy, D.: Prophet-type inequalities for multichoice optimal stopping. Stoch. Process. Appl. 24(1), 77\u201388 (1987)","journal-title":"Stoch. Process. Appl."},{"key":"21_CR24","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA, pp. 630\u2013631 (2005)"},{"issue":"1","key":"21_CR25","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1287\/opre.46.1.17","volume":"46","author":"AJ Kleywegt","year":"1998","unstructured":"Kleywegt, A.J., Papastavrou, J.D.: The dynamic and stochastic knapsack problem. Oper. Res. 46(1), 17\u201335 (1998)","journal-title":"Oper. Res."},{"key":"21_CR26","unstructured":"Korula, N., Pal, M.: Algorithms for secretary problems on graphs and hypergraphs. CoRR (2008). arXiv:0807.1139"},{"issue":"1","key":"21_CR27","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"key":"21_CR28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2307\/2985407","volume":"10","author":"DV Lindley","year":"1961","unstructured":"Lindley, D.V.: Dynamic programming and decision theory. Appl. Stat. 10, 39\u201351 (1961)","journal-title":"Appl. Stat."},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: FOCS, pp. 426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"21_CR30","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: A statistical adversary for on-line algorithms. In: Online Algorithms, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 53, pp. 79\u201383 (1991)","DOI":"10.1090\/dimacs\/007\/05"},{"issue":"3","key":"21_CR32","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"DJ Rosenkrantz","year":"1977","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563\u2013581 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR33","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. In: FSTTCS, pp. 5\u201319 (2006)","DOI":"10.1007\/11944836_3"},{"issue":"1","key":"21_CR35","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"NE Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. J. Algorithms 37(1), 218\u2013235 (2000)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0021-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0021-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0021-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T01:17:48Z","timestamp":1566955068000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0021-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,7]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["21"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0021-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,7]]}}}