{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:48:27Z","timestamp":1725828507384},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_57","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"680-692","source":"Crossref","is-referenced-by-count":5,"title":["Online Appointment Scheduling in the Random Order Model"],"prefix":"10.1007","author":[{"given":"Oliver","family":"G\u00f6bel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"T\u00f6nnis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F.N., Bampis, E., Chekuri, C., Karger, D.R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proc. 40th Symp. Foundations of Computer Science (FOCS), pp. 32\u201344 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"issue":"4","key":"57_CR2","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S. Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Operations Research\u00a062(4), 876\u2013890 (2014)","journal-title":"Operations Research"},{"issue":"1","key":"57_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0895480195290017","volume":"14","author":"M. Ajtai","year":"2001","unstructured":"Ajtai, M., Megiddo, N., Waarts, O.: Improved algorithms and analysis for secretary problems and generalizations. SIAM J. Discrete Math.\u00a014(1), 1\u201327 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"57_CR4","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proc. 18th Symp. Discr. Algorithms (SODA), pp. 434\u2013443 (2007)"},{"issue":"2","key":"57_CR5","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1287\/moor.1110.0489","volume":"36","author":"M.A. Begen","year":"2011","unstructured":"Begen, M.A., Queyranne, M.: Appointment scheduling with discrete random durations. Math. Oper. Res.\u00a036(2), 240\u2013257 (2011)","journal-title":"Math. Oper. Res."},{"key":"57_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res.\u00a034(2), 270\u2013286 (2009)","DOI":"10.1287\/moor.1080.0363"},{"key":"57_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1007\/3-540-48224-5_69","volume-title":"Automata, Languages and Programming","author":"C. Chekuri","year":"2001","unstructured":"Chekuri, C., Khanna, S.: A PTAS for minimizing weighted completion time on uniformly related machines. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 848\u2013861. Springer, Heidelberg (2001)"},{"issue":"1","key":"57_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0204-7","volume":"119","author":"J.R. Correa","year":"2009","unstructured":"Correa, J.R., Wagner, M.R.: Lp-based online scheduling: from single to parallel machines. Math. Program.\u00a0119(1), 109\u2013136 (2009)","journal-title":"Math. Program."},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proc. 10th Conf. Electr. Commerce (EC), pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"57_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: Proc. 12th Conf. Electr. Commerce (EC), pp. 29\u201338 (2011)","DOI":"10.1145\/1993574.1993581"},{"key":"57_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-642-15775-2_16","volume-title":"Algorithms \u2013 ESA 2010","author":"J. Feldman","year":"2010","unstructured":"Feldman, J., Henzinger, M., Korula, N., Mirrokni, V.S., Stein, C.: Online stochastic packing applied to display ad allocation. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 182\u2013194. Springer, Heidelberg (2010)"},{"key":"57_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In: Proc. 26th Symp. Discr. Algorithms (SODA), pp. 1189\u20131201 (2015)","DOI":"10.1137\/1.9781611973730.79"},{"issue":"4","key":"57_CR13","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s002360050162","volume":"36","author":"A. Fiat","year":"1999","unstructured":"Fiat, A., Woeginger, G.J.: On-line scheduling on a single machine: Minimizing the total completion time. Acta Inf.\u00a036(4), 287\u2013293 (1999)","journal-title":"Acta Inf."},{"key":"57_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/978-3-662-43951-7_43","volume-title":"Automata, Languages, and Programming","author":"O. G\u00f6bel","year":"2014","unstructured":"G\u00f6bel, O., Hoefer, M., Kesselheim, T., Schleiden, T., V\u00f6cking, B.: Online independent set beyond the worst-case: Secretaries, prophets, and periods. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol.\u00a08573, pp. 508\u2013519. Springer, Heidelberg (2014)"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"G\u00fcnther, E., Maurer, O., Megow, N., Wiese, A.: A new approach to online scheduling: Approximating the optimal competitive ratio. In: Proc. 24th Symp. Discr. Algorithms (SODA), pp. 118\u2013128 (2013)","DOI":"10.1137\/1.9781611973105.9"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: Primal beats dual on online packing LPs in the random-order model. In: Proc. 46th Symp. Theory of Computing (STOC), pp. 303\u2013312 (2014)","DOI":"10.1145\/2591796.2591810"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proc. 44th Symp. Theory of Computing (STOC), pp. 123\u2013136 (2012)","DOI":"10.1145\/2213977.2213991"},{"key":"57_CR18","doi-asserted-by":"crossref","unstructured":"Lachish, O.: O(log log rank) competitive ratio for the matroid secretary problem. In: Proc. 55th Symp. Foundations of Computer Science (FOCS), pp. 326\u2013335 (2014)","DOI":"10.1109\/FOCS.2014.42"},{"key":"57_CR19","doi-asserted-by":"crossref","unstructured":"Megow, N., Schulz, A.S.: On-line scheduling to minimize average completion time revisited. Oper. Res. Lett., 32(5):485\u2013490 (2004)","DOI":"10.1016\/j.orl.2003.11.008"},{"key":"57_CR20","doi-asserted-by":"crossref","unstructured":"Megow, N., Uetz, M., Vredeveld, T.: Models and algorithms for stochastic online scheduling. Math. Oper. Res., 31(3):513\u2013525 (2006)","DOI":"10.1287\/moor.1060.0201"},{"issue":"4","key":"57_CR21","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1287\/moor.2014.0653","volume":"39","author":"N. Megow","year":"2014","unstructured":"Megow, N., Vredeveld, T.: A tight 2-approximation for preemptive stochastic scheduling. Math. Oper. Res.\u00a039(4), 1297\u20131310 (2014)","journal-title":"Math. Oper. Res."},{"key":"57_CR22","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM 54(5) (2007)","DOI":"10.1145\/1284320.1284321"},{"key":"57_CR23","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proc. 42nd Symp. Foundations of Computer Science (FOCS), pp. 426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"57_CR24","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: The parking permit problem. In: Proc. 46th Symp. Foundations of Computer Science (FOCS), pp. 274\u2013284 (2005)","DOI":"10.1109\/SFCS.2005.72"},{"key":"57_CR25","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.A.: Designing networks incrementally. In: Proc. 42nd Symp. Foundations of Computer Science (FOCS), pp. 406\u2013415 (2001)","DOI":"10.1109\/SFCS.2001.959915"},{"issue":"1","key":"57_CR26","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1287\/moor.2013.0612","volume":"39","author":"M. Molinaro","year":"2014","unstructured":"Molinaro, M., Ravi, R.: The geometry of online packing linear programs. Math. Oper. Res.\u00a039(1), 46\u201359 (2014)","journal-title":"Math. Oper. Res."},{"key":"57_CR27","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A.S. Schulz","year":"2002","unstructured":"Schulz, A.S., Skutella, M.: The power of \u03b1-points in preemptive single machine scheduling. Journal of Scheduling\u00a05, 121\u2013133 (2002)","journal-title":"Journal of Scheduling"},{"issue":"6","key":"57_CR28","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1016\/j.orl.2010.08.012","volume":"38","author":"R. Sitters","year":"2010","unstructured":"Sitters, R.: Competitive analysis of preemptive single-machine scheduling. Operations Research Letters\u00a038(6), 585\u2013588 (2010)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T01:38:19Z","timestamp":1567129099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}