{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T22:05:32Z","timestamp":1759529132348},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> We consider an online model where an adversary constructs a set of [Formula: see text] instances [Formula: see text] instead of one single instance. The algorithm knows [Formula: see text] and the adversary will choose one instance from [Formula: see text] at random to present to the algorithm. We further focus on adversaries that construct sets of [Formula: see text]-chromatic instances. In this setting, we provide upper and lower bounds on the competitive ratio for the online graph coloring problem as a function of the parameters in this model. Both bounds are linear in [Formula: see text] and matching upper and lower bound are given for a specific set of algorithms that we call \u201cminimalistic online algorithms\u201d. <\/jats:p>","DOI":"10.1142\/s0129054118410058","type":"journal-article","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T03:14:49Z","timestamp":1530242089000},"page":"551-569","source":"Crossref","is-referenced-by-count":3,"title":["Online Graph Coloring Against a Randomized Adversary"],"prefix":"10.1142","volume":"29","author":[{"given":"Elisabet","family":"Burjons","sequence":"first","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[{"name":"Department of Computer Science, ETH Zurich, Switzerland"}]},{"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Comenius University, Bratislava, Slovakia"}]},{"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[{"name":"Google Inc., Zurich, Switzerland"}]},{"given":"Xavier","family":"Mu\u00f1oz","sequence":"additional","affiliation":[{"name":"Mathematics Department, UPC, Barcelona, Spain"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[{"name":"Department of Computer Science, RWTH Aachen University, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"S0129054118410058BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9819-7"},{"key":"S0129054118410058BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.006"},{"key":"S0129054118410058BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.01.001"},{"key":"S0129054118410058BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.01.027"},{"key":"S0129054118410058BIB007","volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","year":"1998"},{"key":"S0129054118410058BIB008","doi-asserted-by":"publisher","DOI":"10.1137\/060668675"},{"key":"S0129054118410058BIB011","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2009012"},{"key":"S0129054118410058BIB016","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"S0129054118410058BIB019","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/007\/06"},{"key":"S0129054118410058BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80051-7"},{"key":"S0129054118410058BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2"},{"key":"S0129054118410058BIB022","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011105"},{"key":"S0129054118410058BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30642-6_23"},{"key":"S0129054118410058BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"S0129054118410058BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90096-4"},{"key":"S0129054118410058BIB026","first-page":"79","author":"Raghavan P.","year":"1991","journal-title":"On-line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"S0129054118410058BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90061-G"},{"key":"S0129054118410058BIB030","volume-title":"Introduction to Graph Theory","author":"West Douglas B.","year":"2001","edition":"2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118410058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T15:44:15Z","timestamp":1565106255000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118410058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":18,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,29]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0129054118410058"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118410058","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}