Marek Chrobak

Q: What Schools Are Affiliated With Marek Chrobak

Marek Chrobak is affiliated with the following schools: University of California, Riverside, Stanford University, University of Warsaw

Marek Chrobak's AcademicInfluence.com Rankings

Marek Chrobak

Computer Science

#1721

World Rank

#1782

Historical Rank

Database

#7857

World Rank

#8177

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Marek Chrobak's Degrees

PhD Computer Science Stanford University
Masters Computer Science Stanford University
Bachelors Computer Science Stanford University

Similar Degrees You Can Earn

Why Is Marek Chrobak Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Marek Chrobak is a full professor at University of California, Riverside. He is known for his work competitive analysis of online algorithms, particularly for the k-server problem, on information dissemination in ad-hoc radio networks, and on graph drawing.

(See a Problem?)

Marek Chrobak's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Finite Automata and Unary Languages (1986) (276)
Fast broadcasting and gossiping in radio networks (2000) (262)
New results on server problems (1991) (261)
An Optimal On-Line Algorithm for k-Servers on Trees (1991) (180)
A Linear-Time Algorithm for Drawing a Planar Graph on a Grid (1995) (170)
Competitive analysis of randomized paging algorithms (2000) (151)
Analysis of Bacterial Community Composition by Oligonucleotide Fingerprinting of rRNA Genes (2002) (148)
Reconstructing hv-Convex Polyominoes from Orthogonal Projections (1999) (138)
Dynamic Thermal Management through Task Scheduling (2008) (137)
Convex Grid Drawings of 3-Connected Planar Graphs (1997) (125)
Planar Orientations with Low Out-degree and Compaction of Adjacency Matrices (1991) (120)
Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs (2004) (112)
The Server Problem and On-Line Games (1991) (97)
Probe selection algorithms with applications in the analysis of microbial communities (2001) (92)
LRU Is Better than FIFO (1999) (90)
Minimum-width grid drawings of plane graphs (1994) (85)
Reducing Large Internet Topologies for Faster Simulations (2005) (85)
Convex drawings of graphs in two and three dimensions (preliminary version) (1996) (82)
The wake-up problem in multi-hop radio networks (2004) (81)
On Some Packing Problem Related to Dynamic Storage Allocation (1988) (77)
The greedy algorithm for the minimum common string partition problem (2005) (72)
Polynomial-time algorithms for minimum energy scheduling (2009) (70)
Generosity helps, or an 11–competitive algorithm for three servers (1992) (69)
Improved online algorithms for buffer management in QoS switches (2004) (68)
Sampling large Internet topologies for simulation purposes (2007) (64)
Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help (2004) (63)
Caching Is Hard—Even in the Fault Model (2012) (58)
A Note on Scheduling Equal-Length Jobs to Maximize Throughput (2004) (55)
Group Search on the Line (2015) (54)
Errata to: "finite automata and unary languages" (2003) (54)
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems (2008) (53)
SIGACT news online algorithms column 8 (2005) (52)
Page Migration Algorithms Using Work Functions (1993) (51)
The reverse greedy algorithm for the metric k-median problem (2005) (49)
Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms (1998) (48)
A randomized algorithm for gossiping in radio networks (2001) (46)
SIGACT news online algorithms column 10: competitiveness via doubling (2006) (44)
Better Approximation Bounds for the Joint Replenishment Problem (2013) (40)
A lower bound on the size of universal sets for planar graphs (1989) (39)
The complexity of mean flow time scheduling problems with release times (2006) (38)
Preemptive scheduling in overloaded systems (2002) (36)
Incremental Medians via Online Bidding (2005) (35)
The 3-server problem in the plane (1999) (34)
The weighted 2-server problem (2000) (33)
A Data Structure Useful for Finding Hamiltonian Cycles (1990) (31)
Optimal Parallel 5-Colouring of Planar Graphs (1989) (31)
Performance-aware thermal management via task scheduling (2010) (30)
Competive Analysis of Randomized Paging Algorithms (1996) (30)
On Fast Algorithms for Two Servers (1990) (29)
Improved Edge-Coloring Algorithms for Planar Graphs (1990) (29)
A New Approach to the Server Problem (1991) (27)
The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts (2001) (27)
Metrical Task Systems, the Server Problem and the Work Function Algorithm (1996) (26)
A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem (1997) (26)
PRISE (PRImer SElector): software for designing sequence-selective PCR primers. (2008) (26)
Approximation algorithms for the joint replenishment problem with deadlines (2012) (26)
Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines (2007) (25)
Online Algorithms for Multi-Level Aggregation (2015) (24)
Hierarchies of One-Way Multihead Automata Languages (1985) (24)
Preemptive scheduling of equal-length jobs to maximize weighted throughput (2002) (24)
Fast Algorithms for Edge-Coloring Planar Graphs (1989) (23)
Unique decipherability for partially commutative alphabet (1986) (22)
A Randomized Algorithm for Two Servers on the Line (2000) (22)
A low-cost memory remapping scheme for address bus protection (2006) (22)
Approximation algorithms for the Fault-Tolerant Facility Placement problem (2011) (21)
Collecting Weighted Items from a Dynamic Queue (2009) (18)
On tiling under tomographic constraints (2003) (17)
Oblivious Medians Via Online Bidding (2006) (17)
Multi-Query Diversification in Microblogging Posts (2014) (17)
Faster Algorithms for k-Medians in Trees (2003) (16)
Harmonic is 3-Competitive for Two Servers (1992) (16)
Computing simple paths among obstacles (2000) (16)
k+1 heads are better than k for PDA's (1986) (16)
Solution of a problem in DNA computing (2002) (15)
Polynomial Time Algorithms for Minimum Energy Scheduling (2007) (15)
Parallel 5-Colouring of Planar Graphs (1987) (15)
Policy-Aware Topologies for Efficient Inter-Domain Routing Evaluations (2008) (15)
Randomized competitive algorithms for online buffer management in the adaptive adversary model (2011) (14)
PRISE2: Software for designing sequence-selective PCR primers and probes (2014) (14)
LP-rounding algorithms for the fault-tolerant facility placement problem (2012) (13)
More on random walks, electrical networks, and the harmonic k-server algorithm (2002) (13)
SIGACT news online algorithms column 17 (2010) (12)
Online Control Message Aggregation in Chain Networks (2013) (12)
The k-Median Problem for Directed Trees (2001) (12)
Algorithms for Placing Monitors in a Flow Network (2009) (12)
Competitive algorithms for multilevel caching and relaxed list update (1998) (11)
SIGACT news online algorithms column 1 (2003) (11)
Competitiveness via Doubling (2006) (11)
SIGACT news online algorithms column 13: 2007 - an offine perspective (2008) (11)
Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs (1989) (10)
A Randomized Algorithm for Two Servers on the Line (Extended Abstract) (1998) (10)
Caching Is Hard—Even in the Fault Model (2010) (10)
SIGACT news online algorithms column 4 (2004) (10)
Online Packet Scheduling with Bounded Delay and Lookahead (2016) (10)
More on randomized on-line algorithms for caching (2003) (10)
Randomized Algorithms for Buffer Management with 2-Bounded Delay (2009) (9)
Better bounds for incremental medians (2007) (9)
Two-Bounded-Space Bin Packing Revisited (2011) (9)
A simple analysis of the harmonic algorithm for two servers (2000) (9)
Coordination mechanisms for congestion games (2004) (9)
Algorithmic Aspects of Energy-Efficient Computing (2012) (8)
Three results on frequency assignment in linear cellular networks (2009) (8)
A greedy approximation algorithm for minimum-gap scheduling (2013) (7)
A Note on Bounded-Reversal Multipushdown Machines (1984) (7)
Online Clique Clustering (2014) (7)
A φ-Competitive Algorithm for Scheduling Packets with Deadlines (2018) (7)
A princess swimming in the fog looking for a monster cow (2004) (7)
On common edges in optimal solutions to traveling salesman and other optimization problems (1988) (6)
Competitive Algorithms for Relaxed List Update and Multilevel Caching (2000) (6)
Online aggregation problems (2014) (6)
Obtaining Provably Legitimate Internet Topologies (2012) (6)
A ϕ-competitive algorithm for collecting items with increasing weights from a dynamic queue (2013) (6)
A Note on Tiling under Tomographic Constraints (2001) (5)
Nondeterminism Is Essential for Two-Way Counter Machines (1984) (5)
Optimal Search Trees with 2-Way Comparisons (2015) (5)
Improved Probe Selection for DNA Arrays Using Nonparametric Kernel Density Estimation (2005) (5)
Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the Average Flow Time (2004) (5)
Online medians via online bribery (2006) (5)
Efficient sequential and parallel algorithms for computing recovery points in trees and paths (1991) (5)
A Simple Algorithm for Optimal Search Trees with Two-way Comparisons (2021) (4)
Remarks on String-Matching and One-Way Multihead Automata (1987) (4)
Online Algorithms for Multilevel Aggregation (2020) (4)
A Note on the Server Problem and a Benevolent Adversary (1991) (4)
Competitiveness via primal-dual (2007) (4)
Variations on the Technique of Duris and Galil (1985) (4)
Competitive Analysis of Scheduling Algorithms for Aggregated Links (2008) (4)
Unique Deciperability for Partially Commutative Alphabet (Extended Abstract) (1996) (4)
Two Results on Linear Embeddings of Complete Binary Trees (1994) (4)
New Results on the Fault-Tolerant Facility Placement Problem (2011) (4)
Scheduling with gaps: new models and algorithms (2014) (4)
Slowing the Firehose: Multi-Dimensional Diversity on Social Post Streams (2016) (3)
Better bounds for incremental frequency allocation in bipartite graphs (2011) (3)
Better Bounds for Online Line Chasing (2018) (3)
A Note on NP-Hardness of Preemptive Mean Flow-Time Scheduling for Parallel Machines (2014) (3)
Information Gathering in Ad-Hoc Radio Networks with Tree Topology (2014) (3)
A Note on Random Sampling (1988) (3)
On Huang and Wong’s algorithm for generalized binary split trees (2019) (3)
Competitive Strategies for Online Clique Clustering (2014) (3)
A note on $${\mathbb {NP}}$$NP-hardness of preemptive mean flow-time scheduling for parallel machines (2014) (2)
Fast Parallel and Sequential Algorithms for Edge-Coloring Planar Graphs (1988) (2)
An efficient parallel algorithm for computing a large independent set in a plan graph (1989) (2)
LRU Is Better than FIFO 1 (2)
Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability (2018) (2)
An efficient parallel algorithm for computing a large independent set in a planar graph (1991) (2)
Analysis of microbial community composition using oligonucleotide fingerprinting of 1 ribosomal RNA genes 2 3 Running Title : Oligonucleotide fingerprinting of ribosomal RNA genes 4 5 (2)
Faster Information Gathering in Ad-Hoc Radio Tree Networks (2015) (2)
Faster Algorithms for k-Medians in Trees (Extended Abstract) (2003) (2)
Analysis of the Harmonic Algorithm for Three Servers (2003) (2)
Connectivity vs. Reachability (1991) (2)
On the Cost of Unsuccessful Searches in Search Trees with Two-way Comparisons (2021) (2)
A Characterization of Reversal-Bounded Multipushdown Machine Languages (1985) (2)
Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract). (1998) (1)
New results on multi-level aggregation (2021) (1)
title=New Results on Server Problems. (1990) (1)
SIGACT news online algorithms column 2 (2004) (1)
An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs (2019) (1)
Algorithms for testing fault-tolerance of sequenced jobs (2009) (1)
The k-Median Problem for Directed Trees Extended Abstract (2001) (1)
Competitive Analysis of Scheduling Algorithms for Aggregated Links (2006) (1)
Saturating Flows in Networks (1987) (1)
Experimental Analysis of Scheduling Algorithms for Aggregated Links (2009) (1)
SIGACT news online algorithms column 14 (2009) (1)
Optimal search trees with equality tests (2015) (1)
Approximation algorithms for the joint replenishment problem with deadlines (2014) (1)
A Waste-Efficient Algorithm for Single-Droplet Sample Preparation on Microfluidic Chips (2019) (1)
Sequence Decision Diagrams (2014) (1)
A $\phi$-Competitive Algorithm for Scheduling Packets with Deadlines (2018) (1)
Faster Information Gathering in Ad-Hoc Radio Tree Networks (2017) (1)
Oblivious Medians Via Online Bidding (Extended Abstract) (2006) (1)
A $\boldsymbol{\phi }$ -Competitive Algorithm for Scheduling Packets with Deadlines (2022) (0)
Work-Function Algorithm for k-Servers (2016) (0)
Work-Function Algorithm for k -Servers (2008) (0)
A Note on Tiling under Tomographi ConstraintsMarek Chrobak (2007) (0)
SIGACT news online algorithms column 16 (2010) (0)
Algorithm DC-Tree for k-Servers on Trees (2016) (0)
Competitive algorithms for packet scheduling in computer networks (2006) (0)
Together or Separate? Algorithmic Aggregation Problems (2013) (0)
Classification via two-way comparisons (2023) (0)
On the Volume and Resolution of 3-Dimensional Convex Graph Drawing ( Extended Abstract ) (2007) (0)
Online Paging with Heterogeneous Cache Slots (2022) (0)
Approximation Algorithms for Clique Clustering (2014) (0)
Introduction to the SIGACT news online algorithms column (2010) (0)
Preemptive S heduling in OverloadedSystems (2002) (0)
Algorithms for Placing Monitors in a Flow Network (2012) (0)
Open problems in automata theory related to complexity theory (1986) (0)
Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments (2007) (0)
Page Migration Algorithms Using Work Functions (extended Abstract) (1993) (0)
2005: an offline persepctive (2006) (0)
A greedy approximation algorithm for minimum-gap scheduling (2016) (0)
Bibliography on Competitive Algorithms (1996) (0)
Probabilistic Turing Machines and Recursively Enumerable Dedekind Cuts (1984) (0)
Algorithms for Sensor Systems - 12th International Symposium, ALGOSENSORS 2016, Aarhus, Denmark, August 25-26, 2016, Proceedings (2017) (0)
Generalized Whac-a-Mole (2008) (0)
A generalization of Smith's theorem (1987) (0)
The 3-Server Problem in the plane (extended abstract) (1999) (0)
Online Clique Clustering (2019) (0)
SIGACT News Online Algorithms Colum n1 0 (2006) (0)
Better Hardness Results for the Minimum Spanning Tree Congestion Problem (2022) (0)
Collecting Weighted Items from a Dynamic Queue (2011) (0)
Algorithm DC-Tree for kServers on Trees (2008) (0)
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 (2017) (0)
8 Conjectures and Open Problems Algorithm Dfwf. (distributed Flush-when-full) 7.1 Lower Bound the Cover Problem. Theorem 18 for Every N-processor Network N, for Every Sequence of Operations (2008) (0)
2 7 A pr 2 00 5 Online Medians via Online Bribery ( Extended Abstract ) (2008) (0)
Work-Function Algorithm for k Servers (2008) (0)
Tile-Packing Tomography Is \mathbbNP{\mathbb{NP}}-hard (2010) (0)
Modeling Fluid Mixing in Microfluidic Grids (2019) (0)
Cross-chain Swaps with Preferences (2022) (0)
SIGACT news online algorithms column 19 (2011) (0)
Two results of complete on linear embeddings binary trees (2001) (0)
Tile-Packing Tomography Is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{NP}$\end{document}-hard (2011) (0)
Tile Packing Tomography is NP-hard (2009) (0)
An LP-Rounding Algorithm for Degenerate Primer Design (2014) (0)
Errata to Analysis of the Harmonic Algorithm for Three Servers (2004) (0)
Paths Among Points Inside a Simple Polygon ( Extended Abstract ) (2008) (0)
Preemptive S heduling in Overloaded Systems ( Extended Abstra t ) (2002) (0)
Tile-Packing Tomography Is $\mathbb{NP}$-hard (2009) (0)
Information Gathering in Ad-Hoc Radio Networks (2019) (0)
PRISE2: Software for designing sequence-selective PCR primers and probes (2014) (0)

This paper list is powered by the following services:

Other Resources About Marek Chrobak

What Schools Are Affiliated With Marek Chrobak?

Marek Chrobak is affiliated with the following schools:

Marek Chrobak's Academic­Influence.com Rankings