Marek Chrobak

According to our database1, Marek Chrobak authored at least 157 papers between 1984 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability (Extended Abstract).
Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2016
Work-Function Algorithm for k-Servers.
Encyclopedia of Algorithms, 2016

Algorithm DC-Tree for k-Servers on Trees.
Encyclopedia of Algorithms, 2016

Faster Information Gathering in Ad-Hoc Radio Tree Networks.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Online Packet Scheduling with Bounded Delay and Lookahead.
Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

Online Algorithms for Multi-Level Aggregation.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Slowing the Firehose: Multi-Dimensional Diversity on Social Post Streams.
Proceedings of the 19th International Conference on Extending Database Technology, 2016

2015
A note on NP-hardness of preemptive mean flow-time scheduling for parallel machines.
J. Scheduling, 2015

Group Search on the Line.
Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

Optimal Search Trees with 2-Way Comparisons.
Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Scheduling with Gaps: New Models and Algorithms.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

Competitive Strategies for Online Clique Clustering.
Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014
Online aggregation problems.
SIGACT News, 2014

PRISE2: Software for designing sequence-selective PCR primers and probes.
BMC Bioinformatics, 2014

An LP-Rounding Algorithm for Degenerate Primer Design.
Proceedings of the Algorithms in Bioinformatics - 14th International Workshop, 2014

Sequence Decision Diagrams.
Proceedings of the String Processing and Information Retrieval, 2014

Better Approximation Bounds for the Joint Replenishment Problem.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Multi-Query Diversification in Microblogging Posts.
Proceedings of the 17th International Conference on Extending Database Technology, 2014

Information Gathering in Ad-Hoc Radio Networks with Tree Topology.
Proceedings of the Combinatorial Optimization and Applications, 2014

2013
A ϕ-competitive algorithm for collecting items with increasing weights from a dynamic queue.
Theor. Comput. Sci., 2013

Online Control Message Aggregation in Chain Networks.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Approximation Algorithms for the Joint Replenishment Problem with Deadlines.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Together or Separate? Algorithmic Aggregation Problems.
Proceedings of the Fundamentals of Computation Theory - 19th International Symposium, 2013

LP-Rounding Algorithms for the Fault-Tolerant Facility Placement Problem.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012
Algorithmic Aspects of Energy-Efficient Computing.
Proceedings of the Handbook of Energy-Aware and Green Computing - Two Volume Set., 2012

Obtaining Provably Legitimate Internet Topologies.
IEEE/ACM Trans. Netw., 2012

Tile-Packing Tomography Is NP-hard.
Algorithmica, 2012

2011
Randomized competitive algorithms for online buffer management in the adaptive adversary model.
Theor. Comput. Sci., 2011

SIGACT news online algorithms column 19.
SIGACT News, 2011

Approximation algorithms for the Fault-Tolerant Facility Placement problem.
Inf. Process. Lett., 2011

Two-Bounded-Space Bin Packing Revisited.
Proceedings of the Algorithms - ESA 2011, 2011

Better Bounds for Incremental Frequency Allocation in Bipartite Graphs.
Proceedings of the Algorithms - ESA 2011, 2011

2010
Performance-aware thermal management via task scheduling.
TACO, 2010

SIGACT news online algorithms column 17.
SIGACT News, 2010

SIGACT news online algorithms column 16.
SIGACT News, 2010

A low-cost memory remapping scheme for address bus protection.
J. Parallel Distrib. Comput., 2010

Caching Is Hard - Even in the Fault Model.
Proceedings of the Algorithms, 2010

Polynomial Time Algorithms for Minimum Energy Scheduling.
Proceedings of the Scheduling, 14.02. - 19.02.2010, 2010

Tile-Packing Tomography Is \mathbbNP{\mathbb{NP}}-hard.
Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

2009
Introduction to the SIGACT news online algorithms column.
SIGACT News, 2009

SIGACT news online algorithms column 14.
SIGACT News, 2009

Algorithms for testing fault-tolerance of sequenced jobs.
J. Scheduling, 2009

Collecting weighted items from a dynamic queue.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Three Results on Frequency Assignment in Linear Cellular Networks.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

Algorithms for Placing Monitors in a Flow Network.
Proceedings of the Algorithmic Aspects in Information and Management, 2009

2008
Work-Function Algorithm for k Servers.
Proceedings of the Encyclopedia of Algorithms, 2008

Algorithm DC-Tree for kServers on Trees.
Proceedings of the Encyclopedia of Algorithms, 2008

SIGACT news online algorithms column 13: 2007 - an offine perspective.
SIGACT News, 2008

Incremental Medians via Online Bidding.
Algorithmica, 2008

Experimental Analysis of Scheduling Algorithms for Aggregated Links.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Randomized Algorithms for Buffer Management with 2-Bounded Delay.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

Dynamic Thermal Management through Task Scheduling.
Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2008

Policy-Aware Topologies for Efficient Inter-Domain Routing Evaluations.
Proceedings of the INFOCOM 2008. 27th IEEE International Conference on Computer Communications, 2008

Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems.
Proceedings of the Algorithmic Aspects in Information and Management, 2008

2007
Competitiveness via primal-dual.
SIGACT News, 2007

The Wake-Up Problem in MultiHop Radio Networks.
SIAM J. Comput., 2007

The complexity of mean flow time scheduling problems with release times.
J. Scheduling, 2007

Sampling large Internet topologies for simulation purposes.
Computer Networks, 2007

Better Bounds for Incremental Medians.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Fast Algorithms for Testing Fault-Tolerance of Sequenced Jobs with Deadlines.
Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 2007

Polynomial Time Algorithms for Minimum Energy Scheduling.
Proceedings of the Algorithms, 2007

Algorithmic Approaches to Selecting Control Clones in DNA Array Hybridization Experiments.
Proceedings of 5th Asia-Pacific Bioinformatics Conference, 2007

2006
SIGACT news online algorithms column 10: competitiveness via doubling.
SIGACT News, 2006

2005: an offline persepctive.
SIGACT News, 2006

A Note on Scheduling Equal-Length Jobs to Maximize Throughput.
J. Scheduling, 2006

Online competitive algorithms for maximizing weighted throughput of unit jobs.
J. Discrete Algorithms, 2006

Competitive Analysis of Scheduling Algorithms for Aggregated Links.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Oblivious Medians Via Online Bidding.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

A low-cost memory remapping scheme for address bus protection.
Proceedings of the 15th International Conference on Parallel Architectures and Compilation Techniques (PACT 2006), 2006

2005
SIGACT news online algorithms column 8.
SIGACT News, 2005

Reducing Large Internet Topologies for Faster Simulations.
Proceedings of the NETWORKING 2005: Networking Technologies, 2005

The Reverse Greedy Algorithm for the Metric K-Median Problem.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004
Coordination mechanisms for congestion games.
SIGACT News, 2004

SIGACT news online algorithms column 4.
SIGACT News, 2004

A princess swimming in the fog looking for a monster cow.
SIGACT News, 2004

SIGACT news online algorithms column 2.
SIGACT News, 2004

Preemptive scheduling of equal-length jobs to maximize weighted throughput.
Oper. Res. Lett., 2004

Errata to Analysis of the Harmonic Algorithm for Three Servers.
Proceedings of the STACS 2004, 2004

Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.
Proceedings of the STACS 2004, 2004

The wake-up problem in multi-hop radio networks.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Improved Online Algorithms for Buffer Management in QoS Switches.
Proceedings of the Algorithms, 2004

The Greedy Algorithm for the Minimum Common String Partition Problem.
Proceedings of the Approximation, 2004

2003
More on randomized on-line algorithms for caching.
Theor. Comput. Sci., 2003

On tiling under tomographic constraints.
Theor. Comput. Sci., 2003

SIGACT news online algorithms column 1.
SIGACT News, 2003

Analysis of the Harmonic Algorithm for Three Servers.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Faster Algorithms for k-Medians in Trees.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002
Solution of a problem in DNA computing.
Theor. Comput. Sci., 2002

More on random walks, electrical networks, and the harmonic k-server algorithm.
Inf. Process. Lett., 2002

Preemptive Scheduling in Overloaded Systems.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001
The k-Median Problem for Directed Trees.
Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Probe selection algorithms with applications in the analysis of microbial communities.
Proceedings of the Ninth International Conference on Intelligent Systems for Molecular Biology, 2001

The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

A Randomized Algorithm for Gossiping in Radio Networks.
Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000
Competitive analysis of randomized paging algorithms.
Theor. Comput. Sci., 2000

Competitive Algorithms for Relaxed List Update and Multilevel Caching.
J. Algorithms, 2000

A simple analysis of the harmonic algorithm for two servers.
Inf. Process. Lett., 2000

A Randomized Algorithm for Two Servers on the Line.
Inf. Comput., 2000

Computing simple paths among obstacles.
Comput. Geom., 2000

The Weighted 2-Server Problem.
Proceedings of the STACS 2000, 2000

Fast Broadcasting and Gossiping in Radio Networks.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Reconstructing hv-Convex Polyominoes from Orthogonal Projections.
Inf. Process. Lett., 1999

The 3-Server Problem in the Plane.
Proceedings of the Algorithms, 1999

1998
Competive Algorithms for Multilevel Caching and Relaxed List Update (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

LRU is Better than FIFO.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

A Randomized Algorithm for Two Servers on the Line (Extended Abstract).
Proceedings of the Algorithms, 1998

1997
A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem.
Inf. Process. Lett., 1997

Convex Grid Drawings of 3-Connected Planar Graphs.
Int. J. Comput. Geometry Appl., 1997

1996
Competive Analysis of Randomized Paging Algorithms.
Proceedings of the Algorithms, 1996

Bibliography on Competitive Algorithms.
Proceedings of the Online Algorithms, 1996

Metrical Task Systems, the Server Problem and the Work Function Algorithm.
Proceedings of the Online Algorithms, 1996

Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version).
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
A Linear-Time Algorithm for Drawing a Planar Graph on a Grid.
Inf. Process. Lett., 1995

1994
Two Results on Linear Embeddings of Complete Binary Trees.
Theor. Comput. Sci., 1994

Generosity Helps or an 11-Competitive Algorithm for Three Servers.
J. Algorithms, 1994

Minimum-Width Grid Drawings of Plane Graphs.
Proceedings of the Graph Drawing, DIMACS International Workshop, 1994

1993
Page Migration Algorithms Using Work Functions.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992
Harmonic is 3-Competitive for Two Servers.
Theor. Comput. Sci., 1992

Generosity Helps, or an 11-Competitive Algorithm for Three Servers.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991
Connectivity vs. Reachability
Inf. Comput., April, 1991

Planar Orientations with Low Out-degree and Compaction of Adjacency Matrices.
Theor. Comput. Sci., 1991

A New Approach to the Server Problem.
SIAM J. Discrete Math., 1991

An Optimal On-Line Algorithm for k-Servers on Trees.
SIAM J. Comput., 1991

A Note on the Server Problem and a Benevolent Adversary.
Inf. Process. Lett., 1991

An Efficient Parallel Algorithm for Computing a Large Independent Set in Planar Graph.
Algorithmica, 1991

Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

The Server Problem and On-Line Games.
Proceedings of the On-Line Algorithms, 1991

1990
A Data Structure Useful for Finding Hamiltonian Cycles.
Theor. Comput. Sci., 1990

Improved Edge-Coloring Algorithms for Planar Graphs.
J. Algorithms, 1990

New Results on Server Problems.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

On Fast Algorithms for Two Servers.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989
A lower bound on the size of universal sets for planar graphs.
SIGACT News, 1989

Optimal Parallel 5-Colouring of Planar Graphs.
SIAM J. Comput., 1989

Fast Algorithms for Edge-Coloring Planar Graphs.
J. Algorithms, 1989

Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs.
Proceedings of the Algorithms and Data Structures, 1989

An Efficient Parallel Algorithm for Computing a Large Independent Set in a Plan Graph.
Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988
k+1 Heads Are Better than k for PDAs.
J. Comput. Syst. Sci., 1988

On Some Packing Problem Related to Dynamic Storage Allocation.
ITA, 1988

A Note on Random Sampling.
Inf. Process. Lett., 1988

On common edges in optimal solutions to traveling salesman and other optimization problems.
Discrete Applied Mathematics, 1988

Fast Parallel and Sequential Algorithms for Edge-Coloring Planar Graphs.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Remarks on String-Matching and One-Way Multihead Automata.
Inf. Process. Lett., 1987

Parallel 5-Colouring of Planar Graphs.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Saturating Flows in Networks.
Proceedings of the Fundamentals of Computation Theory, 1987

1986
Finite Automata and Unary Languages.
Theor. Comput. Sci., 1986

Unique Deciperability for Partially Commutative Alphabet (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

k+1 Heads Are Better than k for PDA's
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
A Characterization of Reversal-Bounded Multipushdown Machine Languages.
Theor. Comput. Sci., 1985

Variations on the Technique of Duris and Galil.
J. Comput. Syst. Sci., 1985

Hierarchies of One-Way Multihead Automata Languages.
Proceedings of the Automata, 1985

1984
Probabilistic Turing Machines and Recursively Enumerable Dedekind Cuts.
Inf. Process. Lett., 1984

A Note on Bounded-Reversal Multipushdown Machines.
Inf. Process. Lett., 1984

Nondeterminism Is Essential for Two-Way Counter Machines.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984


  Loading...