Arrow Research search

Author name cluster

Marek Chrobak

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

40 papers
2 author rows

Possible papers

40

SODA Conference 2019 Conference Paper

A ϕ-Competitive Algorithm for Scheduling Packets with Deadlines

  • Pavel Veselý 0001
  • Marek Chrobak
  • Lukasz Jez
  • Jirí Sgall

In the online packet scheduling problem with deadlines (PacketScheduling, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so, if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets which are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketScheduling, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a ϕ -competitive online algorithm for PacketScheduling (where ϕ ≈ 1. 618 is the golden ratio), matching the previously established lower bound.

Details

MFCS Conference 2019 Conference Paper

Better Bounds for Online Line Chasing

  • Marcin Bienkowski
  • Jaroslaw Byrka
  • Marek Chrobak
  • Christian Coester
  • Lukasz Jez
  • Elias Koutsoupias

We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, .. ., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1, .. ., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28. 1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1. 5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1. 412 for convex body chasing in 2 dimensions.

Details

SODA Conference 2014 Conference Paper

Better Approximation Bounds for the Joint Replenishment Problem

  • Marcin Bienkowski
  • Jaroslaw Byrka
  • Marek Chrobak
  • Lukasz Jez
  • Dorian Nogneng
  • Jirí Sgall

The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer ρ has a fixed cost c ρ. In addition, we incur waiting costs for each order, possibly an arbitrary non-decreasing function of time, different for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1. 8. This ratio can be reduced to ≈ 1. 574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is ℙ -hard and that the natural linear program for JRP has integrality gap at least 1. 245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2. 64 and 3, respectively. The lower bound of 2. 64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio ≈ 1. 791, breaking the barrier of 1. 8. We also show that the integrality gap of the linear program for JRP-L is at least 12/11 ≈ 1. 09. In the online case, we show a lower bound of ≈ 2. 754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2. 64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.

Details

MFCS Conference 2003 Conference Paper

Faster Algorithms for k -Medians in Trees

  • Robert Benkoczi
  • Binay K. Bhattacharya
  • Marek Chrobak
  • Lawrence L. Larmore
  • Wojciech Rytter

Abstract In the k -median problem we are given a connected graph with non-negative weights associated with the nodes and lengths associated with the edges. The task is to compute locations of k facilities in order to minimize the sum of the weighted distances between each node and its closest facility. In this paper we consider the case when the graph is a tree. We show that this problem can be solved in time \(O(n {\mbox{\rm polylog}} (n))\) for the following cases: (i) directed trees (and any fixed k ), (ii) balanced undirected trees, and (iii) undirected trees with k =3.

Details

MFCS Conference 2001 Conference Paper

The k-Median Problem for Directed Trees

  • Marek Chrobak
  • Lawrence L. Larmore
  • Wojciech Rytter

Abstract The k -median problem is a classical facility location problem. We consider the k -median problem for directed trees, motivated by the problem of locating proxies on the World Wide Web. The two main results of the paper are an O(n log n) time algorithm for k=2 and an O(n log 2 n) time algorithm for k=3. The previously known upper bounds for these two cases were O ( n 2 ).

Details

FOCS Conference 2000 Conference Paper

Fast Broadcasting and Gossiping in Radio Networks

  • Marek Chrobak
  • Leszek Gasieniec
  • Wojciech Rytter

We establish an O(n log/sup 2/n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of /spl Omega/(n log n). The fastest previously known algorithm for this problem works in time O(n/sup 3/2/). Using our broadcasting algorithm, we develop an O(n/sup 3/2/log/sup 2/n) algorithm for gossiping in the same network model.

Details

MFCS Conference 1998 Conference Paper

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

  • Marek Chrobak
  • Christoph Dürr

Abstract We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dimension D ≥2, whose points may be occupied by c distinct types of atoms. To “analyze” T, we conduct ℓ measurements that we call discrete X-rays. A discrete X-ray in direction ξ determines the number of atoms of each type on each line parallel to ξ. Given ℓ such non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c =1 (one atom type) has been completely determined by Gardner, Gritzmann and Prangerberg [5], who proved that the problem is NP-complete for any dimension D ≥ 2 and ℓ ≥ 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise [8]. The NP-completeness result above clearly extends to any c ≥ 2, and therefore when studying the polyatomic case we can assume that ℓ = 2. As shown in another article by the same authors, [4], this problem is also NP-complete for c ≥ 6 atoms, even for dimension D = 2 and axis-parallel X-rays. The authors of [4] conjecture that the problem remains NP-complete for c =3, 4, 5, although, as they point out, the proof idea in [4] does not seem to extend to c ≤ 5. We resolve the conjecture from [4] by proving that the problem is indeed NP-complete for c ≥ 3 in 2D, even for axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0–1 matrices with given row and column sums.

Details

MFCS Conference 1990 Conference Paper

On Fast Algorithms for Two Servers

  • Marek Chrobak
  • Lawrence L. Larmore

Abstract We consider 2-server algorithms with time complexity O (1) per each request. We show that the previously known algorithm BALANCE2 has competitiveness constant not better than 6, and present another algorithm whose competitiveness constant is 4.

Details

FOCS Conference 1986 Conference Paper

k+1 Heads Are Better than k for PDA's

  • Marek Chrobak
  • Ming Li 0001

We resolve the following long-standing conjecture of Harrison and Ibarra in 1968 [HI, p. 462]: There are languages accepted by (k+1)-head 1-way deterministic pushdown automata ((k+1)-DPDA) but not by k-head 1-way pushdown automata (k-PDA), for every k. (Partial solutions for this conjecture can be found in [M1, M2, C].) On the assumption that their conjecture holds, [HI] also derived many important consequences. Now all those consequences become theorems. For example, the class of languages accepted by k-PDA's is not closed under ∩ and complementation. Several other interesting consequences also follow: CFL ⊆∪kDPDA(k) and FA(2)⊆∪kDPDA(k), where DPDA (k)={L|L is accepted by a k-DPDA} and FA(2)={L|L is accepted by a 2-head FA). Our new proof itself is also interesting in the sense that the k+l versus k heads problems was solved by diagonalization methods [I2, M2, M3, M4, S] for stronger machines (2-way, etc). and by traditional counting arguments [S2, IK, YR, M1] for weaker machines (k-FA, k-head counter machine, etc).

Details

MFCS Conference 1986 Conference Paper

Unique Deciperability for Partially Commutative Alphabet (Extended Abstract)

  • Marek Chrobak
  • Wojciech Rytter

Abstract We consider the unique decipherability problem for partially commutative alphabet. It is shown that the complexity of this problem depends heavily on the size of the alphabet and the structure of the commutativity relation graph. In particular, for alphabets with ≤3 letters the problem is decidable and for alphabets with ≥4 letters the problem is undecidable.

Details