Marek Chrobak
Person information
- affiliation: University of California, Riverside, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2019
- [c80]Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines. SODA 2019: 123-142 - [i32]Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young:
On Huang and Wong's Algorithm for Generalized Binary Split Trees. CoRR abs/1901.03783 (2019) - 2018
- [j100]Marek Chrobak, Kevin P. Costello:
Faster Information Gathering in Ad-Hoc Radio Tree Networks. Algorithmica 80(3): 1013-1040 (2018) - [j99]Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Dariusz R. Kowalski:
Information gathering in ad-hoc radio networks with tree topology. Inf. Comput. 258: 1-27 (2018) - [i31]Miguel Coviello Gonzalez, Marek Chrobak:
Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability. CoRR abs/1806.08875 (2018) - [i30]Pavel Veselý, Marek Chrobak, Lukasz Jez, Jirí Sgall:
A φ-Competitive Algorithm for Scheduling Packets with Deadlines. CoRR abs/1807.07177 (2018) - [i29]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Lukasz Jez, Elias Koutsoupias:
Better Bounds for Online Line Chasing. CoRR abs/1811.09233 (2018) - 2017
- [j98]Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor:
A greedy approximation algorithm for minimum-gap scheduling. J. Scheduling 20(3): 279-292 (2017) - [e1]Marek Chrobak, Antonio Fernández Anta, Leszek Gasieniec, Ralf Klasing:
Algorithms for Sensor Systems - 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2016, Aarhus, Denmark, August 25-26, 2016, Revised Selected Papers. Lecture Notes in Computer Science 10050, Springer 2017, ISBN 978-3-319-53057-4 [contents] - 2016
- [c79]Shiwen Cheng, Marek Chrobak, Vagelis Hristidis:
Slowing the Firehose: Multi-Dimensional Diversity on Social Post Streams. EDBT 2016: 17-28 - [c78]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, Pavel Veselý:
Online Algorithms for Multi-Level Aggregation. ESA 2016: 12:1-12:17 - [c77]Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý:
Online Packet Scheduling with Bounded Delay and Lookahead. ISAAC 2016: 21:1-21:13 - [c76]Marek Chrobak, Kevin P. Costello:
Faster Information Gathering in Ad-Hoc Radio Tree Networks. LATIN 2016: 275-289 - [r5]
- [r4]
- [i28]Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý:
Online Packet Scheduling with Bounded Delay and Lookahead. CoRR abs/1606.09395 (2016) - 2015
- [j97]Li Yan, Marek Chrobak:
LP-rounding algorithms for the fault-tolerant facility placement problem. J. Discrete Algorithms 33: 93-114 (2015) - [j96]Odile Bellenguez-Morineau, Marek Chrobak, Christoph Dürr, Damien Prot:
A note on NP-hardness of preemptive mean flow-time scheduling for parallel machines. J. Scheduling 18(3): 299-304 (2015) - [j95]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young:
Approximation algorithms for the joint replenishment problem with deadlines. J. Scheduling 18(6): 545-560 (2015) - [c75]Marek Chrobak, Christoph Dürr, Bengt J. Nilsson:
Competitive Strategies for Online Clique Clustering. CIAC 2015: 101-113 - [c74]Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng:
Scheduling with Gaps: New Models and Algorithms. CIAC 2015: 114-126 - [c73]Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young:
Optimal Search Trees with 2-Way Comparisons. ISAAC 2015: 71-82 - [c72]Marek Chrobak, Leszek Gasieniec, Thomas Gorry, Russell Martin:
Group Search on the Line. SOFSEM 2015: 164-176 - [i27]Marek Chrobak, Mordecai J. Golin, J. Ian Munro, Neal E. Young:
Optimal search trees with equality tests. CoRR abs/1505.00357 (2015) - [i26]Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jirí Sgall, Nguyen Kim Thang, Pavel Veselý:
Online Algorithms for Multi-Level Aggregation. CoRR abs/1507.02378 (2015) - [i25]Marek Chrobak, Kevin P. Costello:
Faster Information Gathering in Ad-Hoc Radio Tree Networks. CoRR abs/1512.02179 (2015) - 2014
- [j94]Francis Y. L. Chin, Marek Chrobak, Li Yan:
Algorithms for Placing Monitors in a Flow Network. Algorithmica 68(1): 1-15 (2014) - [j93]Yu-Ting Huang, Jiue-in Yang, Marek Chrobak, James Borneman:
PRISE2: Software for designing sequence-selective PCR primers and probes. BMC Bioinformatics 15: 317 (2014) - [j92]
- [c71]Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Darek Kowalski:
Information Gathering in Ad-Hoc Radio Networks with Tree Topology. COCOA 2014: 129-145 - [c70]Shiwen Cheng, Anastasios Arvanitis, Marek Chrobak, Vagelis Hristidis:
Multi-Query Diversification in Microblogging Posts. EDBT 2014: 133-144 - [c69]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Dorian Nogneng, Jirí Sgall:
Better Approximation Bounds for the Joint Replenishment Problem. SODA 2014: 42-54 - [c68]
- [c67]Yu-Ting Huang, Marek Chrobak:
An LP-Rounding Algorithm for Degenerate Primer Design. WABI 2014: 107-121 - [i24]Odile Bellenguez-Morineau, Marek Chrobak, Christoph Dürr, Damien Prot:
A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines. CoRR abs/1404.5424 (2014) - [i23]Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Dariusz R. Kowalski:
Information Gathering in Ad-Hoc Radio Networks with Tree Topology. CoRR abs/1407.1521 (2014) - [i22]Marek Chrobak, Mordecai J. Golin, Tak Wah Lam, Dorian Nogneng:
Scheduling with Gaps: New Models and Algorithms. CoRR abs/1410.7092 (2014) - [i21]Marek Chrobak, Christoph Dürr, Bengt J. Nilsson:
Approximation Algorithms for Clique Clustering. CoRR abs/1411.4274 (2014) - 2013
- [j91]Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
Collecting Weighted Items from a Dynamic Queue. Algorithmica 65(1): 60-94 (2013) - [j90]Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
A ϕ-competitive algorithm for collecting items with increasing weights from a dynamic queue. Theor. Comput. Sci. 475: 92-102 (2013) - [j89]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better bounds for incremental frequency allocation in bipartite graphs. Theor. Comput. Sci. 514: 75-83 (2013) - [c66]Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor:
A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC 2013: 97-109 - [c65]
- [c64]
- [c63]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, Neal E. Young:
Approximation Algorithms for the Joint Replenishment Problem with Deadlines. ICALP (1) 2013: 135-147 - [c62]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall, Grzegorz Stachowiak:
Online Control Message Aggregation in Chain Networks. WADS 2013: 133-145 - [i20]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Approximation Bounds for the Joint Replenishment Problem. CoRR abs/1307.2531 (2013) - 2012
- [j88]Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu:
Caching Is Hard - Even in the Fault Model. Algorithmica 63(4): 781-794 (2012) - [j87]Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Nguyen Kim Thang:
Tile-Packing Tomography Is NP-hard. Algorithmica 64(2): 267-278 (2012) - [j86]Philippe Baptiste, Marek Chrobak, Christoph Dürr:
Polynomial-time algorithms for minimum energy scheduling. ACM Trans. Algorithms 8(3): 26:1-26:29 (2012) - [j85]Yihua He, Michalis Faloutsos, Srikanth V. Krishnamurthy, Marek Chrobak:
Obtaining Provably Legitimate Internet Topologies. IEEE/ACM Trans. Netw. 20(1): 271-284 (2012) - [r3]Marek Chrobak:
Algorithmic Aspects of Energy-Efficient Computing. Handbook of Energy-Aware and Green Computing 2012: 311-329 - [i19]Li Yan, Marek Chrobak:
LP-rounding Algorithms for the Fault-Tolerant Facility Placement Problem. CoRR abs/1205.1281 (2012) - [i18]Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak:
Approximation Algorithms for the Joint Replenishment Problem with Deadlines. CoRR abs/1212.3233 (2012) - 2011
- [j84]Li Yan, Marek Chrobak:
Approximation algorithms for the Fault-Tolerant Facility Placement problem. Inf. Process. Lett. 111(11): 545-549 (2011) - [j83]
- [j82]Marek Chrobak, Mathilde Hurand:
Better bounds for incremental medians. Theor. Comput. Sci. 412(7): 594-601 (2011) - [j81]Marcin Bienkowski, Marek Chrobak, Lukasz Jez:
Randomized competitive algorithms for online buffer management in the adaptive adversary model. Theor. Comput. Sci. 412(39): 5121-5131 (2011) - [c61]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. ESA 2011: 251-262 - [c60]Marek Chrobak, Jirí Sgall, Gerhard J. Woeginger:
Two-Bounded-Space Bin Packing Revisited. ESA 2011: 263-274 - [i17]Marek Chrobak, Lukasz Jez, Jirí Sgall:
Better Bounds for Incremental Frequency Allocation in Bipartite Graphs. CoRR abs/1102.3393 (2011) - [i16]Li Yan, Marek Chrobak:
New Results on the Fault-Tolerant Facility Placement Problem. CoRR abs/1108.5471 (2011) - 2010
- [j80]Jun Yang, Lan Gao, Youtao Zhang, Marek Chrobak, Hsien-Hsin S. Lee:
A low-cost memory remapping scheme for address bus protection. J. Parallel Distrib. Comput. 70(5): 443-457 (2010) - [j79]
- [j78]
- [j77]Xiuyi Zhou, Jun Yang, Marek Chrobak, Youtao Zhang:
Performance-aware thermal management via task scheduling. TACO 7(1): 5:1-5:31 (2010) - [j76]Marek Chrobak, Jirí Sgall:
Three results on frequency assignment in linear cellular networks. Theor. Comput. Sci. 411(1): 131-137 (2010) - [c59]Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Nguyen Kim Thang:
Tile-Packing Tomography Is \mathbbNP{\mathbb{NP}}-hard. COCOON 2010: 254-263 - [c58]Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, Haifeng Xu:
Caching Is Hard - Even in the Fault Model. ESA (1) 2010: 195-206 - [i15]Marek Chrobak, Philippe Baptiste, Christoph Dürr:
Polynomial Time Algorithms for Minimum Energy Scheduling. Scheduling 2010
2000 – 2009
- 2009
- [j75]Marek Chrobak, Mathilde Hurand, Jirí Sgall:
Algorithms for testing fault-tolerance of sequenced jobs. J. Scheduling 12(5): 501-515 (2009) - [j74]
- [j73]Marek Chrobak:
Introduction to the SIGACT news online algorithms column. SIGACT News 40(4): 98 (2009) - [c57]Francis Y. L. Chin, Marek Chrobak, Li Yan:
Algorithms for Placing Monitors in a Flow Network. AAIM 2009: 114-128 - [c56]Marek Chrobak, Jirí Sgall:
Three Results on Frequency Assignment in Linear Cellular Networks. AAIM 2009: 129-139 - [c55]Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Grzegorz Stachowiak:
Collecting weighted items from a dynamic queue. SODA 2009: 1126-1135 - [i14]Philippe Baptiste, Marek Chrobak, Christoph Dürr:
Polynomial Time Algorithms for Minimum Energy Scheduling. CoRR abs/0908.3505 (2009) - [i13]Francis Y. L. Chin, Marek Chrobak, Li Yan:
Algorithms for Placing Monitors in a Flow Network. CoRR abs/0908.4309 (2009) - [i12]Marek Chrobak, Christoph Dürr, Flavio Guiñez, Antoni Lozano, Nguyen Kim Thang:
Tile Packing Tomography is NP-hard. CoRR abs/0911.2567 (2009) - 2008
- [j72]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young:
Incremental Medians via Online Bidding. Algorithmica 50(4): 455-478 (2008) - [j71]Wojciech Jawor, Marek Chrobak, Christoph Dürr:
Competitive Analysis of Scheduling Algorithms for Aggregated Links. Algorithmica 51(4): 367-386 (2008) - [j70]Marek Chrobak:
SIGACT news online algorithms column 13: 2007 - an offine perspective. SIGACT News 39(3): 96-121 (2008) - [c54]Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert:
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems. AAIM 2008: 120-130 - [c53]Yihua He, Michalis Faloutsos, Srikanth V. Krishnamurthy, Marek Chrobak:
Policy-Aware Topologies for Efficient Inter-Domain Routing Evaluations. INFOCOM 2008: 2342-2350 - [c52]Jun Yang, Xiuyi Zhou, Marek Chrobak, Youtao Zhang, Lingling Jin:
Dynamic Thermal Management through Task Scheduling. ISPASS 2008: 191-201 - [c51]Marcin Bienkowski, Marek Chrobak, Lukasz Jez:
Randomized Algorithms for Buffer Management with 2-Bounded Delay. WAOA 2008: 92-104 - [c50]Wojciech Jawor, Marek Chrobak, Mart Molle:
Experimental Analysis of Scheduling Algorithms for Aggregated Links. WAOA 2008: 253-266 - [r2]
- [r1]
- [i11]Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert:
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems. CoRR abs/0801.4238 (2008) - [i10]Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, Lukasz Jez, Jakub Lopuszanski, Grzegorz Stachowiak:
Generalized Whac-a-Mole. CoRR abs/0802.1685 (2008) - 2007
- [j69]Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Jun-Hong Cui, Li Lao, Allon G. Percus:
Sampling large Internet topologies for simulation purposes. Computer Networks 51(15): 4284-4302 (2007) - [j68]Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young:
Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments. J. Bioinformatics and Computational Biology 5(4): 937-961 (2007) - [j67]Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd:
The complexity of mean flow time scheduling problems with release times. J. Scheduling 10(2): 139-146 (2007) - [j66]Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski:
The Wake-Up Problem in MultiHop Radio Networks. SIAM J. Comput. 36(5): 1453-1471 (2007) - [j65]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. SIAM J. Comput. 36(6): 1709-1728 (2007) - [j64]
- [j63]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Improved online algorithms for buffer management in QoS switches. ACM Trans. Algorithms 3(4): 50 (2007) - [c49]Qi Fu, Elizabeth Bent, James Borneman, Marek Chrobak, Neal E. Young:
Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments. APBC 2007: 17-26 - [c48]Philippe Baptiste, Marek Chrobak, Christoph Dürr:
Polynomial Time Algorithms for Minimum Energy Scheduling. ESA 2007: 136-150 - [c47]Marek Chrobak, Mathilde Hurand, Jirí Sgall:
Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines. RTSS 2007: 139-148 - [c46]
- 2006
- [j62]Marek Chrobak, Claire Kenyon, Neal E. Young:
The reverse greedy algorithm for the metric k-median problem. Inf. Process. Lett. 97(2): 68-72 (2006) - [j61]Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms 4(2): 255-276 (2006) - [j60]Marek Chrobak, Christoph Dürr, Wojciech Jawor, Lukasz Kowalik, Maciej Kurowski:
A Note on Scheduling Equal-Length Jobs to Maximize Throughput. J. Scheduling 9(1): 71-73 (2006) - [j59]
- [j58]Marek Chrobak, Claire Kenyon-Mathieu:
SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News 37(4): 115-126 (2006) - [c45]Lan Gao, Jun Yang, Marek Chrobak, Youtao Zhang, San Nguyen, Hsien-Hsin S. Lee:
A low-cost memory remapping scheme for address bus protection. PACT 2006: 74-83 - [c44]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young:
Oblivious Medians Via Online Bidding. LATIN 2006: 311-322 - [c43]Wojciech Jawor, Marek Chrobak, Christoph Dürr:
Competitive Analysis of Scheduling Algorithms for Aggregated Links. LATIN 2006: 617-628 - [i9]Philippe Baptiste, Peter Brucker, Marek Chrobak, Christoph Dürr, Svetlana A. Kravchenko, Francis Sourd:
The Complexity of Mean Flow Time Scheduling Problems with Release Times. CoRR abs/cs/0605078 (2006) - 2005
- [j57]
- [j56]Marek Chrobak, Petr Kolman, Jirí Sgall:
The greedy algorithm for the minimum common string partition problem. ACM Trans. Algorithms 1(2): 350-366 (2005) - [c42]Marek Chrobak, Claire Kenyon, Neal E. Young:
The Reverse Greedy Algorithm for the Metric K-Median Problem. COCOON 2005: 654-660 - [c41]Vaishnavi Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Li Lao, Jun-Hong Cui, Allon G. Percus:
Reducing Large Internet Topologies for Faster Simulations. NETWORKING 2005: 328-341 - [i8]Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young:
Oblivious Medians via Online Bidding. CoRR abs/cs/0504103 (2005) - [i7]Marek Chrobak, Claire Kenyon, Neal E. Young:
The reverse greedy algorithm for the metric k-median problem. CoRR abs/cs/0504104 (2005) - 2004
- [j55]Marek Chrobak, Leszek Gasieniec, Wojciech Rytter:
A randomized algorithm for gossiping in radio networks. Networks 43(2): 119-124 (2004) - [j54]Philippe Baptiste, Marek Chrobak, Christoph Dürr, Wojciech Jawor, Nodari Vakhania:
Preemptive scheduling of equal-length jobs to maximize weighted throughput. Oper. Res. Lett. 32(3): 258-264 (2004) - [j53]
- [j52]Marek Chrobak:
A princess swimming in the fog looking for a monster cow. SIGACT News 35(2): 74-78 (2004) - [j51]
- [j50]Marek Chrobak, Elias Koutsoupias:
Coordination mechanisms for congestion games. SIGACT News 35(4): 58-71 (2004) - [j49]Marek Chrobak, Jirí Sgall:
The weighted 2-server problem. Theor. Comput. Sci. 324(2-3): 289-312 (2004) - [c40]Marek Chrobak, Petr Kolman, Jirí Sgall:
The Greedy Algorithm for the Minimum Common String Partition Problem. APPROX-RANDOM 2004: 84-95 - [c39]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Improved Online Algorithms for Buffer Management in QoS Switches. ESA 2004: 204-215 - [c38]Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý:
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. ICALP 2004: 358-370 - [c37]