{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:12:03Z","timestamp":1764936723854},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_43","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T04:37:49Z","timestamp":1402461469000},"page":"508-519","source":"Crossref","is-referenced-by-count":16,"title":["Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods"],"prefix":"10.1007","author":[{"given":"Oliver","family":"G\u00f6bel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Hoefer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schleiden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","unstructured":"Akcoglu, K., Aspnes, J., DasGupta, B., Kao, M.-Y.: Opportunity cost algorithms for combinatorial auctions. CoRR, cs.CE\/0010031 (2000)"},{"key":"43_CR2","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: Proc. 13th EC, pp. 18\u201335 (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"43_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-74208-1_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Babaioff","year":"2007","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.D.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 16\u201328. Springer, Heidelberg (2007)"},{"key":"43_CR4","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proc. 18th SODA, pp. 434\u2013443 (2007)"},{"key":"43_CR5","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 EC, pp. 29\u201338 (2011)","DOI":"10.1145\/1993574.1993581"},{"key":"43_CR6","first-page":"627","volume":"4","author":"E.B. Dynkin","year":"1963","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl\u00a04, 627\u2013629 (1963)","journal-title":"Sov. Math. Dokl"},{"issue":"6","key":"43_CR7","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput.\u00a034(6), 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"Fangh\u00e4nel, A., Geulen, S., Hoefer, M., V\u00f6cking, B.: Online capacity maximization in wireless networks. In: Proc. 22nd SPAA, pp. 92\u201399 (2010)","DOI":"10.1145\/1810479.1810499"},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"Feldman, J., Henzinger, M., Korula, N., Mirrokni, V.S., Stein, C.: Online stochastic packing applied to display ad allocation. In: Proc. 18th ESA, pp. 182\u2013194 (2010)","DOI":"10.1007\/978-3-642-15775-2_16"},{"key":"43_CR10","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proc. 5th British Combinatorial Conference, pp. 211\u2013226 (1975)"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"G\u00f6bel, O., Hoefer, M., Kesselheim, T., Schleiden, T., V\u00f6cking, B.: Online independent set beyond the worst-case: Secretaries, prophets, and periods. CoRR, abs\/1307.3192 (2013)","DOI":"10.1007\/978-3-662-43951-7_43"},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"Goussevskaia, O., Wattenhofer, R., Halld\u00f3rsson, M.M., Welzl, E.: Capacity of arbitrary wireless networks. In: Proc. 28th INFOCOM, pp. 1872\u20131880 (2009)","DOI":"10.1109\/INFCOM.2009.5062108"},{"key":"43_CR13","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Kleinberg, R., Parkes, D.C.: Adaptive limited-supply online auctions. In: Proc. 5th EC, pp. 71\u201380 (2004)","DOI":"10.1145\/988772.988784"},{"key":"43_CR14","unstructured":"Hajiaghayi, M., Kleinberg, R.D., Sandholm, T.: Automated online mechanism design and prophet inequalities. In: Proc. 22nd AAAI, pp. 58\u201365 (2007)"},{"key":"43_CR15","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Holzer, S., Mitra, P., Wattenhofer, R.: The power of non-uniform wireless power. In: Proc. 24th SODA, pp. 1595\u20131606 (2013)","DOI":"10.1137\/1.9781611973105.114"},{"key":"43_CR16","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Mitra, P.: Wireless capacity with oblivious power in general metrics. In: Proc. 22nd SODA, pp. 1538\u20131548 (2011)","DOI":"10.1137\/1.9781611973082.119"},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Hoefer, M., Kesselheim, T., V\u00f6cking, B.: Approximation algorithms for secondary spectrum auctions. In: Proc. 23rd SPAA, pp. 177\u2013186 (2011)","DOI":"10.1145\/1989493.1989520"},{"issue":"1","key":"43_CR18","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S. Irani","year":"1994","unstructured":"Irani, S.: Coloring inductive graphs on-line. Algorithmica\u00a011(1), 53\u201372 (1994)","journal-title":"Algorithmica"},{"key":"43_CR19","doi-asserted-by":"crossref","unstructured":"Kesselheim, T.: A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In: Proc. SODA, pp. 1549\u20131559 (2011)","DOI":"10.1137\/1.9781611973082.120"},{"key":"43_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-642-40450-4_50","volume-title":"Algorithms \u2013 ESA 2013","author":"T. Kesselheim","year":"2013","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 589\u2013600. Springer, Heidelberg (2013)"},{"key":"43_CR21","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 STOC (2014)","DOI":"10.1145\/2591796.2591810"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proc. 44th STOC, pp. 123\u2013136 (2012)","DOI":"10.1145\/2213977.2213991"},{"issue":"2","key":"43_CR23","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G. Koren","year":"1995","unstructured":"Koren, G., Shasha, D.: \n                    \n                      \n                    \n                    $\\text{D}^{\\textit{over}}$\n                  : An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J. Comput.\u00a024(2), 318\u2013339 (1995)","journal-title":"SIAM J. Comput."},{"key":"43_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-642-02930-1_42","volume-title":"Automata, Languages and Programming","author":"N. Korula","year":"2009","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 508\u2013520. Springer, Heidelberg (2009)"},{"key":"43_CR25","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1090\/S0002-9904-1977-14378-4","volume":"83","author":"U. Krengel","year":"1977","unstructured":"Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Amer. Math. Soc.\u00a083, 745\u2013747 (1977)","journal-title":"Bull. Amer. Math. Soc."},{"key":"43_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/978-3-642-31594-7_59","volume-title":"Automata, Languages, and Programming","author":"M. Molinaro","year":"2012","unstructured":"Molinaro, M., Ravi, R.: Geometry of online packing linear programs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 701\u2013713. Springer, Heidelberg (2012)"},{"key":"43_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1007\/978-3-642-02927-1_64","volume-title":"Automata, Languages and Programming","author":"Y. Ye","year":"2009","unstructured":"Ye, Y., Borodin, A.: Elimination graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 774\u2013785. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:07:47Z","timestamp":1558908467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}