Arrow Research search

Author name cluster

Jirí Sgall

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.

14 papers
1 author row

Possible papers

14

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

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 1994 Invited Paper

On-Line Scheduling of Parallel Jobs

  • Jirí Sgall

Abstract We survey theoretical results on scheduling of parallel jobs when only partial information about them is available. We study how the length of the schedule changes under the influence of various factors, such as the use of randomization, the presence of dependencies between jobs, the choice of a network topology, the use of virtualization, and the maximal size of jobs. We give tight or very close upper and lower bounds on the best possible performance of on-line scheduling algorithms for many combinations of these factors, thus giving an essentially complete picture of how they interact and influence the performance and methods for scheduling.

Details

FOCS Conference 1991 Conference Paper

Communication Complexity Towards Lower Bounds on Circuit Depth

  • Jeff Edmonds
  • Steven Rudich
  • Russell Impagliazzo
  • Jirí Sgall

M. Karchmer et al. (1991) considered the circuit depth complexity of n-bit Boolean function constructed by composing up to d=log n/log log n levels of k=log-n-bit Boolean functions. Any such function is in AC/sup 1/. They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires dk in Omega (log/sup 2/ n/log log n) depth. This would separate AC/sup 1/ from NC/sup 1/. They recommend using the communication game characterization of circuit depth. They suggest an intermediate problem which they call the universal composition relation. An almost optimal lower bound of dk-O(d/sup 2/(k log k)/sup 1/2/) is given for this problem. In addition, a proof, directly in terms of communication complexity, that there is a function on k bits requiring Omega (k) circuit depth is presented. >

Details

FOCS Conference 1991 Conference Paper

Dynamic Scheduling on Parallel Machines

  • Anja Feldmann
  • Jirí Sgall
  • Shang-Hua Teng

The problem of online job scheduling on various parallel architectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given. >

Details