Mathilde Hurand

TCS Journal 2013 Journal Article

A ϕ -competitive algorithm for collecting items with increasing weights from a dynamic queue

• Marcin Bienkowski
• Marek Chrobak
• Christoph Dürr
• Mathilde Hurand
• Artur Jeż
• Łukasz Jeż
• Grzegorz Stachowiak

The bounded-delay packet scheduling (or buffer management) problem is to schedule transmissions of packets arriving in a buffer of a network link. Each packet has a deadline and a weight associated with it. The objective is to maximize the weight of packets that are transmitted before their deadlines, assuming that only one packet can be transmitted in one time step. Online packet scheduling algorithms have been extensively studied. It is known that no online algorithm can achieve a competitive ratio better than ϕ ≈ 1. 618 (the golden ratio), while the currently best upper bound on the competitive ratio is 2 2 − 1 ≈ 1. 824. Closing the gap between these bounds remains a major open problem. The above mentioned lower bound of ϕ uses instances where item weights increase exponentially over time. In fact, all lower bounds for various versions of buffer management problems involve instances of this type. In this paper, we design an online algorithm for packet scheduling with competitive ratio ϕ when packet weights are increasing, thus matching this lower bound. Our algorithm applies, in fact, to a much more general version of packet scheduling, where only the relative order of the deadlines is known, not their exact values.

TCS Journal 2011 Journal Article

Better bounds for incremental medians

• Marek Chrobak
• Mathilde Hurand

In the incremental version of the well-known k - m e d i a n p r o b l e m, the objective is to compute an incremental sequence of facility sets F 1 ⊆ F 2 ⊆ ⋯ ⊆ F n, where each F k contains at most k facilities. We say that this incremental medians sequence is R -competitive if the cost of each F k is at most R times the optimum cost of k facilities. The smallest such R is called the competitive ratio of the sequence { F k }. Mettu and Plaxton [Ramgopal R. Mettu, C. Greg Plaxton, The online median problem, in: Proc. 41st Symposium on Foundations of Computer Science, FOCS, IEEE, 2000, pp. 339–348; Ramgopal R. Mettu, C. Greg Plaxton, The online median problem, SIAM Journal on Computing 32 (3) (2003) 816–832] presented a polynomial-time algorithm that computes an incremental sequence with competitive ratio ≈30. They also showed a lower bound of 2. The upper bound on the ratio was improved to 8 in [Guolong Lin, Chandrashekha Nagarajan, Rajmohan Rajamaran, David P. Williamson, A general approach for incremental approximation and hierarchical clustering, in: Proc. 17th Symposium on Discrete Algorithms, SODA, 2006, pp. 1147–1156] and [Marek Chrobak, Claire Kenyon, John Noga, Neal Young, Online medians via online bidding, in: Proc. 7th Latin American Theoretical Informatics Symposium, LATIN, in: Lecture Notes in Computer Science, vol. 3887, 2006, pp. 311–322]. We improve both bounds in this paper. We first show that no incremental sequence can have competitive ratio better than 2. 01 and we give a probabilistic construction of a sequence whose competitive ratio is at most 2 + 4 2 ≈ 7. 656. We also propose a new approach to the problem that for instances that we refer to as equable achieves an optimal ratio of 2.

SODA Conference 2009 Conference Paper

Collecting weighted items from a dynamic queue

• Marcin Bienkowski
• Marek Chrobak
• Christoph Dürr
• Mathilde Hurand
• Artur Jez
• Lukasz Jez
• Grzegorz Stachowiak