Author name cluster

Jiřı́ 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.

5 papers

1 author row

TCS Journal 2004 Journal Article

It is tough to be a plumber

Daniel Král’
Vladan Majerech
Jiřı́ Sgall
Tomáš Tichý
Gerhard Woeginger

In the Linux computer game KPlumber, the objective is to rotate tiles in a raster of squares so as to complete a system of pipes. We give a complexity classification for the original game and various special cases of it that arise from restricting the set of six possible tiles. Most of the cases are NP-complete. One polynomially solvable case is settled by formulating it as a perfect matching problem; other polynomial cases are settled by simple sweepline techniques. Moreover, we show that all the unsettled cases are polynomial time equivalent.

Details DOI

TCS Journal 2004 Journal Article

The weighted 2-server problem

Marek Chrobak
Jiřı́ Sgall

We consider a generalization of the 2-server problem in which servers have different costs. We prove that, in uniform spaces, a version of the work function algorithm is 5-competitive, and that no better ratio is possible. We also give a 5-competitive randomized, memoryless algorithm for uniform spaces, and a matching lower bound. For arbitrary metric spaces, in contrast with the non-weighted case, we prove that there is no memoryless randomized algorithm with finite competitive ratio. We also propose a version of the problem in which a request specifies two points to be covered by the servers, and the algorithm must decide which server to move to which point. For this version, we show a 9-competitive algorithm and we prove that no better ratio is possible.

Details DOI

TCS Journal 2002 Journal Article

Off-line temporary tasks assignment

Yossi Azar
Oded Regev
Jiřı́ Sgall
Gerhard J. Woeginger

In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time. We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i. e. , not fixed), no polynomial algorithm can achieve a better approximation ratio than 3 2 unless P=NP.

Details DOI

TCS Journal 2002 Journal Article

Solution of a problem in DNA computing

Eric Anderson
Marek Chrobak
John Noga
Jiřı́ Sgall
Gerhard J. Woeginger

We answer a question of Rozenberg and Salomaa arising from a problem in DNA computing. This problem was posed at the ICALP conference in July 1999 in Prague.

Details DOI

TCS Journal 2000 Journal Article

DNF tautologies with a limited number of occurrences of every variable

P. Savický
Jiřı́ Sgall

It is known that every DNF tautology with all monomials of length k contains a variable with at least Ω(2k/k) occurrences. It is not known, however, if this bound is tight, i. e. if there are tautologies with at most O(2k/k) occurrences of every variable. DNF tautologies with 2k monomials of length k and with at most 2k/kα occurrences of every variable, where α=log 3 4−1⩾0. 26 are presented. This has the following consequence. Let (k, s)-SAT be k-SAT restricted to instances with at most s occurrences of every variable. It is known that for every k, there is an sk such that (k, sk)-SAT is NP-complete and (k, sk−1)-SAT is trivial in the sense that every instance has positive answer. The above result implies that sk⩽2k/kα. This improves the previously known bound sk⩽ 13 64 2k for all k⩾6.

Details DOI