☰

Marek Chrobak - Publications

Affiliations: 
University of California, Riverside, Riverside, CA, United States 
Area:
Computer Science
Tree Info Similar researchers PubMed Report error

101 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Bienkowski M, Böhm M, Byrka J, Chrobak M, Dürr C, Folwarczný L, Jeż Ł, Sgall J, Thang NK, Veselý P. Online Algorithms for Multilevel Aggregation Operations Research. 68: 214-232. DOI: 10.1287/Opre.2019.1847  0.448
2020 Gonzalez MC, Chrobak M. Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability Theoretical Computer Science. DOI: 10.1016/J.Tcs.2020.09.007  0.364
2020 Chrobak M, Dürr C, Fabijan A, Nilsson BJ. Online Clique Clustering Algorithmica. 82: 938-965. DOI: 10.1007/S00453-019-00625-1  0.353
2017 Chrobak M, Feige U, Hajiaghayi MT, Khanna S, Li F, Naor S. A greedy approximation algorithm for minimum-gap scheduling Journal of Scheduling. 20: 279-292. DOI: 10.1007/S10951-016-0492-Y  0.479
2016 Chrobak M, Costello KP. Faster information gathering in ad-hoc radio tree networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9644: 275-289. DOI: 10.1007/S00453-017-0336-Y  0.397
2015 Yan L, Chrobak M. LP-rounding algorithms for the fault-tolerant facility placement problem Journal of Discrete Algorithms. 33: 93-114. DOI: 10.1016/J.Jda.2015.03.004  0.451
2015 Bienkowski M, Byrka J, Chrobak M, Dobbs N, Nowicki T, Sviridenko M, Świrszcz G, Young NE. Approximation algorithms for the joint replenishment problem with deadlines Journal of Scheduling. 18: 545-560. DOI: 10.1007/S10951-014-0392-Y  0.421
2015 Bellenguez-Morineau O, Chrobak M, Dürr C, Prot D. A note on (Formula presented)-hardness of preemptive mean flow-time scheduling for parallel machines Journal of Scheduling. 18: 299-304. DOI: 10.1007/S10951-014-0380-2  0.38
2015 Chrobak M, Golin M, Ian Munro J, Young NE. Optimal search trees with 2-Way comparisons Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9472: 71-82. DOI: 10.1007/978-3-662-48971-0_7  0.497
2015 Chrobak M, Golin M, Lam TW, Nogneng D. Scheduling with gaps: New models and algorithms Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9079: 114-126. DOI: 10.1007/978-3-319-18173-8_8  0.472
2014 Chrobak M, Costello K, Gasieniec L, Kowalski DR. Information gathering in ad-hoc radio networks with tree topology Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8881: 129-145. DOI: 10.1016/J.Ic.2017.11.003  0.378
2014 Chin FYL, Chrobak M, Yan L. Algorithms for Placing Monitors in a Flow Network Algorithmica. 68: 1-15. DOI: 10.1007/S00453-012-9665-Z  0.401
2014 Huang YT, Chrobak M. An LP-rounding algorithm for degenerate primer design Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8701: 107-121. DOI: 10.1007/978-3-662-44753-6_9  0.345
2013 Bienkowski M, Chrobak M, Dürr C, Hurand M, Jez A, Jez Ł, Stachowiak G. A φ-competitive algorithm for collecting items with increasing weights from a dynamic queue Theoretical Computer Science. 475: 92-102. DOI: 10.1016/J.Tcs.2012.12.046  0.573
2013 Bienkowski M, Chrobak M, Dürr C, Hurand M, Jez A, Jez Ł, Stachowiak G. Collecting weighted items from a dynamic queue Algorithmica. 65: 60-94. DOI: 10.1007/S00453-011-9574-6  0.448
2013 Chrobak M, Feige U, Taghi Hajiaghayi M, Khanna S, Li F, Naor S. A greedy approximation algorithm for minimum-gap scheduling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7878: 97-109. DOI: 10.1007/978-3-642-38233-8_9  0.454
2012 Baptiste P, Chrobak M, Dürr C. Polynomial-time algorithms for minimum energy scheduling Acm Transactions On Algorithms. 8. DOI: 10.1145/2229163.2229170  0.343
2011 Chrobak M. SIGACT news online algorithms column 19 Sigact News. 42: 82-82. DOI: 10.1145/1998037.1998057  0.526
2011 Chrobak M, Jez Ł, Sgall J. Better bounds for incremental frequency allocation in bipartite graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6942: 251-262. DOI: 10.1016/J.Tcs.2012.05.020  0.417
2011 Bienkowski M, Chrobak M, Jez Ł. Randomized competitive algorithms for online buffer management in the adaptive adversary model Theoretical Computer Science. 412: 5121-5131. DOI: 10.1016/J.Tcs.2011.05.015  0.605
2011 Yan L, Chrobak M. Approximation algorithms for the Fault-Tolerant Facility Placement problem Information Processing Letters. 111: 545-549. DOI: 10.1016/J.Ipl.2011.03.005  0.508
2011 Chrobak M, Sgall J, Woeginger GJ. Two-Bounded-Space bin packing revisited Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6942: 263-274. DOI: 10.1007/978-3-642-23719-5_23  0.338
2010 Chrobak M. SIGACT news online algorithms column 17 Sigact News. 41: 114-121. DOI: 10.1145/1907450.1907547  0.526
2010 Chrobak M. SIGACT news online algorithms column 16 Sigact News. 41: 99-99. DOI: 10.1145/1753171.1753194  0.526
2010 Zhou X, Yang J, Chrobak M, Zhang Y. Performance-aware thermal management via task scheduling Acm Transactions On Architecture and Code Optimization. 7: 5. DOI: 10.1145/1736065.1736070  0.34
2010 Chrobak M. Introduction to the SIGACT news online algorithms column Sigact News. 40: 98. DOI: 10.1145/1711475.1711499  0.469
2010 Chrobak M, Sgall J. Three results on frequency assignment in linear cellular networks Theoretical Computer Science. 411: 131-137. DOI: 10.1016/J.Tcs.2009.09.019  0.442
2009 Chrobak M. SIGACT news online algorithms column 14 Sigact News. 40: 86-98. DOI: 10.1145/1620491.1620508  0.526
2009 Chrobak M, Hurand M, Sgall J. Algorithms for testing fault-tolerance of sequenced jobs Journal of Scheduling. 12: 501-515. DOI: 10.1007/S10951-009-0126-8  0.391
2009 Chrobak M, Sgall J. Three results on frequency assignment in linear cellular Networks (Extended Abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5564: 129-139. DOI: 10.1007/978-3-642-02158-9_12  0.337
2009 Chin F, Chrobak M, Yan L. Algorithms for placing monitors in a flow network (Preliminary Version) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5564: 114-128. DOI: 10.1007/978-3-642-02158-9_11  0.414
2009 Bienkowski M, Chrobak M, Jez Ł. Randomized algorithms for buffer management with 2-bounded delay Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5426: 92-104. DOI: 10.1007/978-3-540-93980-1_8  0.432
2009 Jawor W, Chrobak M, Molle M. Experimental analysis of scheduling algorithms for aggregated links Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5426: 253-266. DOI: 10.1007/978-3-540-93980-1_20  0.433
2008 Chrobak M. SIGACT news online algorithms column 13: 2007 - an offine perspective Sigact News. 39: 96-121. DOI: 10.1145/1412700.1412719  0.495
2008 Chrobak M, Hurand M. Better bounds for incremental medians Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4927: 207-217. DOI: 10.1016/J.Tcs.2009.07.006  0.401
2008 Chrobak M, Dürr C, Hurand M, Robert J. Algorithms for temperature-aware task scheduling in microprocessor systems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5034: 120-130. DOI: 10.1016/J.Suscom.2011.05.009  0.404
2008 Jawor W, Chrobak M, Dürr C. Competitive analysis of scheduling algorithms for aggregated links Algorithmica (New York). 51: 367-386. DOI: 10.1007/S00453-007-9053-2  0.803
2008 Chrobak M, Kenyon C, Noga J, Young NE. Incremental medians via online bidding Algorithmica (New York). 50: 455-478. DOI: 10.1007/S00453-007-9005-X  0.571
2007 Fu Q, Bent E, Borneman J, Chrobak M, Young NE. Algorithmic approaches to selecting control clones in DNA array hybridization experiments. Journal of Bioinformatics and Computational Biology. 5: 937-61. PMID 17787064 DOI: 10.1142/S0219720007002977  0.446
2007 Baptiste P, Chrobak M, Dürr C. Polynomial time algorithms for minimum energy scheduling Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4698: 136-150. DOI: 10.1145/2229163.2229170  0.448
2007 Chrobak M. Competitiveness via primal-dual Sigact News. 38: 100-105. DOI: 10.1145/1324215.1324233  0.506
2007 Chrobak M, Jawor W, Sgall J, Tichý T. Online scheduling of equal-length jobs: Randomization and restarts help Siam Journal On Computing. 36: 1709-1728. DOI: 10.1137/S0097539704446608  0.809
2007 Krishnamurthy V, Faloutsos M, Chrobak M, Cui JH, Lao L, Percus AG. Sampling large Internet topologies for simulation purposes Computer Networks. 51: 4284-4302. DOI: 10.1016/J.Comnet.2007.06.004  0.313
2007 Baptiste P, Brucker P, Chrobak M, Dürr C, Kravchenko SA, Sourd F. The complexity of mean flow time scheduling problems with release times Journal of Scheduling. 10: 139-146. DOI: 10.1007/S10951-006-0006-4  0.48
2007 Fu Q, Bent E, Borneman J, Chrobak M, Young N. Algorithmic approaches to selecting control clones in DNA array hybridization experiments Series On Advances in Bioinformatics and Computational Biology. 5: 17-26.  0.313
2006 Chrobak M, Kenyon-Mathieu C. SIGACT news online algorithms column 10: competitiveness via doubling Sigact News. 37: 115-126. DOI: 10.1145/1189056.1189078  0.515
2006 Chrobak M. 2005: an offline persepctive Sigact News. 37: 82-98. DOI: 10.1145/1122480.1122499  0.521
2006 Chrobak M, Ga̧sieniec L, Kowalski DR. The wake-up problem in multihop radio networks Siam Journal On Computing. 36: 1453-1471. DOI: 10.1137/S0097539704442726  0.334
2006 Chin FYL, Chrobak M, Fung SPY, Jawor W, Sgall J, Tichý T. Online competitive algorithms for maximizing weighted throughput of unit jobs Journal of Discrete Algorithms. 4: 255-276. DOI: 10.1016/J.Jda.2005.03.005  0.805
2006 Chrobak M, Dürr C, Jawor W, Kowalik Ł, Kurowski MI. A note on scheduling equal-length jobs to maximize throughput Journal of Scheduling. 9: 71-73. DOI: 10.1007/S10951-006-5595-4  0.79
2005 Chrobak M. SIGACT news online algorithms column 8 Sigact News. 36: 67-81. DOI: 10.1145/1086649.1086670  0.484
2005 Chrobak M, Kenyon C, Young NE. The reverse greedy algorithm for the metric k-median problem Lecture Notes in Computer Science. 3595: 654-660. DOI: 10.1016/J.Ipl.2005.09.009  0.513
2004 Chrobak M. SIGACT news online algorithms column 2 Sigact News. 35: 38-48. DOI: 10.1145/970831.970841  0.526
2004 Chrobak M, Jawor W, Sgall J, Tichý T. Improved online algorithms for buffer management in QoS Switches Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3221: 204-215. DOI: 10.1145/1290672.1290687  0.799
2004 Chrobak M, Kolman P, Sgall J. The greedy algorithm for the minimum common string partition problem Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3122: 84-95. DOI: 10.1145/1103963.1103971  0.567
2004 Chrobak M, Koutsoupias E. Coordination mechanisms for congestion games Sigact News. 35: 58-71. DOI: 10.1145/1054916.1054933  0.453
2004 Chrobak M. SIGACT news online algorithms column 4 Sigact News. 35: 58-66. DOI: 10.1145/1027914.1027930  0.529
2004 Chrobak M, Sgall J. The weighted 2-server problem Theoretical Computer Science. 324: 289-312. DOI: 10.1016/J.Tcs.2004.05.020  0.584
2004 Baptiste P, Chrobak M, Dürr C, Jawor W, Vakhania N. Preemptive scheduling of equal-length jobs to maximize weighted throughput Operations Research Letters. 32: 258-264. DOI: 10.1016/J.Orl.2003.09.004  0.773
2004 Chrobak M, Sgall J. Errata to analysis of the harmonic algorithm for three servers Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2996: 656. DOI: 10.1007/978-3-540-24749-4_57  0.45
2004 Chrobak M, Ga̧sieniec L, Rytter W. A Randomized Algorithm for Gossiping in Radio Networks Networks. 43: 119-124. DOI: 10.1002/Net.10109  0.567
2003 Chrobak M. SIGACT news online algorithms column 1 Sigact News. 34: 68-77. DOI: 10.1145/954092.954104  0.526
2003 Chrobak M, Couperus P, Dürr C, Woeginger G. On tiling under tomographic constraints Theoretical Computer Science. 290: 2125-2136. DOI: 10.1016/S0304-3975(02)00542-X  0.324
2003 Chrobak M, Koutsoupias E, Noga J. More on randomized on-line algorithms for caching Theoretical Computer Science. 290: 1997-2008. DOI: 10.1016/S0304-3975(02)00045-2  0.6
2003 Benkoczi R, Bhattacharya B, Chrobak M, Larmore LL, Rytter W. Faster algorithms for k-medians in trees: (Extended abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2747: 218-227.  0.326
2002 Bein WW, Chrobak M, Larmore LL. The 3-server problem in the plane Theoretical Computer Science. 289: 335-354. DOI: 10.1016/S0304-3975(01)00305-X  0.439
2002 Chrobak M, Ga̧sieniec L, Rytter W. Fast broadcasting and gossiping in radio networks Journal of Algorithms. 43: 177-189. DOI: 10.1016/S0196-6774(02)00004-4  0.464
2002 Chrobak M, Epstein L, Noga J, Sgall J, Van Stee R, Tichý T, Vakhania N. Preemptive scheduling in overloaded systems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2380: 800-811. DOI: 10.1016/S0022-0000(03)00070-9  0.43
2002 Bartal Y, Chrobak M, Noga J, Raghavan P. More on random walks, electrical networks, and the harmonic k-server algorithm Information Processing Letters. 84: 271-276. DOI: 10.1016/S0020-0190(02)00287-9  0.45
2001 Borneman J, Chrobak M, Vedova GD, Figueroa A, Jiang T. Probe selection algorithms with applications in the analysis of microbial communities Bioinformatics. 17: S39-S48. PMID 11472991 DOI: 10.1093/Bioinformatics/17.Suppl_1.S39  0.401
2001 Chrobak M, Larmore LL, Rytter W. The k-median problem for directed trees Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2136: 260-271.  0.361
2001 Chrobak M, Csirik J, Imreh C, Noga J, Sgall J, Woeginger GJ. The buffer minimization problem for multiprocessor scheduling with conflicts Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2076: 862-874.  0.44
2000 Cheng Q, Chrobak M, Sundaram G. Computing simple paths among obstacles Computational Geometry: Theory and Applications. 16: 223-233. DOI: 10.1016/S0925-7721(00)00011-0  0.442
2000 Achlioptas D, Chrobak M, Noga J. Competitive analysis of randomized paging algorithms Theoretical Computer Science. 234: 203-218. DOI: 10.1016/S0304-3975(98)00116-9  0.534
2000 Chrobak M, Sgall J. Simple analysis of the harmonic algorithm for two servers Information Processing Letters. 75: 75-77. DOI: 10.1016/S0020-0190(00)00070-3  0.482
2000 Chrobak M, Noga J. Competitive Algorithms for Relaxed List Update and Multilevel Caching Journal of Algorithms. 34: 282-308. DOI: 10.1006/Jagm.1999.1061  0.47
1999 Chrobak M, Dürr C. Reconstructing hv-convex polyominoes from orthogonal projections Information Processing Letters. 69: 283-289. DOI: 10.1016/S0020-0190(99)00025-3  0.382
1999 Chrobak M, Noga J. LRU is better than FIFO Algorithmica (New York). 23: 180-185.  0.329
1998 Chrobak M, Larmore LL. Metrical task systems the server problem and the work function algorithm Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1442: 74-96. DOI: 10.1007/Bfb0029565  0.474
1998 Bartal Y, Chrobak M, Larmore LL. A randomized algorithm for two servers on the line Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1461: 247-258. DOI: 10.1006/Inco.1999.2809  0.534
1997 Chrobak M, Kant G. Convex grid drawings of 3-connected planar graphs International Journal of Computational Geometry and Applications. 7: 211-223. DOI: 10.1142/S0218195997000144  0.391
1997 Chrobak M, Larmore LL, Lund C, Reingold N. A better lower bound on the competitive ratio of the randomized 2-server problem Information Processing Letters. 63: 79-83. DOI: 10.1016/S0020-0190(97)00099-9  0.457
1997 Chrobak M, Larmore LL, Reingold N, Westbrook J. Page Migration Algorithms Using Work Functions Journal of Algorithms. 24: 124-157. DOI: 10.1006/Jagm.1996.0853  0.546
1995 Chrobak M, Nakano SI. Minimum-width grid drawings of plane graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 894: 104-110. DOI: 10.1016/S0925-7721(98)00016-9  0.349
1995 Chrobak M, Payne TH. A linear-time algorithm for drawing a planar graph on a grid Information Processing Letters. 54: 241-246. DOI: 10.1016/0020-0190(95)00020-D  0.447
1994 Chrobak M, Rytter W. Two results on linear embeddings of complete binary trees Theoretical Computer Science. 136: 507-526. DOI: 10.1016/0304-3975(94)00036-I  0.496
1994 Chrobak M, Larmore LL. Generosity Helps or an 11-Competitive Algorithm for Three Servers Journal of Algorithms. 16: 234-263. DOI: 10.1006/Jagm.1994.1011  0.572
1992 Chrobak M, Larmore LL. HARMONIC is 3-competitive for two servers Theoretical Computer Science. 98: 339-346. DOI: 10.1016/0304-3975(92)90007-3  0.552
1991 Chrobak M, Karloff H, Payne T, Vishwanathan S. New results on server problems Siam Journal On Discrete Mathematics. 4: 172-181. DOI: 10.1137/0404017  0.549
1991 Chrobak M, Larmore LL. An optimal on-line algorithm for K-servers on trees Siam Journal On Computing. 20: 144-148. DOI: 10.1137/0220008  0.469
1991 Chrobak M, Karloff H, Radzik T. Connectivity vs. reachability Information and Computation. 91: 177-188. DOI: 10.1016/0890-5401(91)90065-A  0.35
1991 Chrobak M, Eppstein D. Planar orientations with low out-degree and compaction of adjacency matrices Theoretical Computer Science. 86: 243-266. DOI: 10.1016/0304-3975(91)90020-3  0.369
1991 Chrobak M, Larmore LL. On fast algorithms for two servers Journal of Algorithms. 12: 607-614. DOI: 10.1016/0196-6774(91)90035-W  0.59
1991 Chrobak M, Larmore LL. A note on the server problem and a benevolent adversary Information Processing Letters. 38: 173-175. DOI: 10.1016/0020-0190(91)90095-Y  0.542
1991 Chrobak M, Naor J. An efficient parallel algorithm for computing a large independent set in a planar graph Algorithmica. 6: 801-815. DOI: 10.1007/Bf01759072  0.525
1990 Chrobak M, Szymacha T, Krawczyk A. A data structure useful for finding Hamiltonian cycles Theoretical Computer Science. 71: 419-424. DOI: 10.1016/0304-3975(90)90053-K  0.378
1990 Chrobak M, Nishizeki T. Improved edge-coloring algorithms for planar graphs Journal of Algorithms. 11: 102-116. DOI: 10.1016/0196-6774(90)90032-A  0.525
1989 Chrobak M, Karloff H. A lower bound on the size of universal sets for planar graphs Sigact News. 20: 83-86. DOI: 10.1145/74074.74088  0.301
1989 Hagerup T, Chrobak M, Diks K. Optimal parallel 5-colouring of planar graphs Siam Journal On Computing. 18: 288-300. DOI: 10.1137/0218020  0.493
1989 Chrobak M, Yung M. Fast algorithms for edge-coloring planar graphs Journal of Algorithms. 10: 35-51. DOI: 10.1016/0196-6774(89)90022-9  0.559
1988 Chrobak M, Slusarek M. On some packing problem related to dynamic storage allocation Theoretical Informatics and Applications. 22: 487-499. DOI: 10.1051/Ita/1988220404871  0.309
Show low-probability matches.