Arrow Research search

Author name cluster

Klaus Jansen

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.

35 papers
2 author rows

Possible papers

35

MFCS Conference 2021 Conference Paper

Fuzzy Simultaneous Congruences

  • Max A. Deppert
  • Klaus Jansen
  • Kim-Manuel Klein

We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer s that is specified by n fixed remainders modulo integer divisors a₁, …, a_n we consider remainder intervals R₁, …, R_n such that s is feasible if and only if s is congruent to r_i modulo a_i for some remainder r_i in interval R_i for all i. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i. e. a_{i+1}/a_i is an integer for all i < n, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time 𝒪(n²) and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time 𝒪(n³).

Details

ICAPS Conference 2021 Conference Paper

Total Completion Time Minimization for Scheduling with Incompatibility Cliques

  • Klaus Jansen
  • Alexandra Lassota
  • Marten Maack
  • Tytus Pikies

This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent years. While the research up to this point has been focused on the makespan objective, we broaden the scope and study the classical total completion time criterion. In the setting without incompatibilities, this objective is well-known to admit polynomial time algorithms even for unrelated machines via matching techniques. We show that the introduction of incompatibility cliques results in a richer, more interesting picture. We prove that scheduling on identical machines remains solvable in polynomial time, while scheduling on unrelated machines becomes APX-hard. Next, we study the problem under the paradigm of fixed-parameter tractable algorithms (FPT). In particular, we consider a problem variant with assignment restrictions for the cliques rather than the jobs. We prove that, despite still being APX-hard, it can be solved in FPT time with respect to the number of cliques. Moreover, we show that the problem on unrelated machines can be solved in FPT time for reasonable parameters, in particular, the parameter combination: maximum processing time, number of job kinds, and number of machines or maximum processing time, number of job kinds, and number of cliques. The latter results are extensions of known results for the case without incompatibilities, and can even be further extended to the case of total weighted completion time. All of the FPT results make use of n-fold Integer Programs that recently received great attention by proving their usefulness for scheduling problems.

Details

SODA Conference 2017 Conference Paper

About the Structure of the Integer Cone and its Application to Bin Packing

  • Klaus Jansen
  • Kim-Manuel Klein

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoß [5] about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time where V is the set of vertices of the integer knapsack poly- tope and enc(I) is the encoding length of the bin packing instance. The algorithm is fixed parameter tractable, parameterized by the number of vertices of the integer knapsack polytope | V |. This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure, i. e. has a small number of vertices. Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound.

Details

SODA Conference 2014 Conference Paper

On the optimality of approximation schemes for the classical scheduling problem

  • Lin Chen 0009
  • Klaus Jansen
  • Guochuan Zhang

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of studies on this problem, focusing on exact and approximation algorithms, and it is thus natural to consider whether these algorithms are best possible in terms of the running time. Under the Exponential Time Hypothesis (ETH), we achieve the following results in this paper: The scheduling problem on a constant number m of identical machines, which is denoted as Pm ‖ C max, is known to admit a fully polynomial time approximation scheme (FPTAS) of running time O ( n ) + (1/∊) O ( m ) (indeed, the algorithm works for an even more general problem where machines are unrelated). We prove this algorithm is essentially the best possible in the sense that a (1/∊) O ( m 1–5 ) + n O (1) time FPTAS for any δ > 0 implies that ETH fails. The scheduling problem on an arbitrary number of identical machines, which is denoted as P ‖ C max, is known to admit a polynomial time approximation scheme (PTAS) of running time 2 O (1/∊ 2 log 3 (1/∊)) + n O (1). We prove this algorithm is nearly optimal in the sense that a 2 O ((1/∊) 1–5 ) + n O (1) time PTAS for any δ > 0 implies that ETH fails, leaving a small room for improvement. In addition, we also consider exact algorithms for the scheduling problem and prove the following result: The traditional dynamic programming algorithm for P ‖ C max is known to run in 2 O ( n ) time. We prove this is essentially the best possible in the sense that even if we restrict that there are n jobs and the processing time of each job is bounded by O ( n ), an exact algorithm of running time 2 (n 1–5 ) for any δ > 0 implies that ETH fails. To obtain these results we will provide two new reductions from 3SAT, one for P ‖ C max and another for P ‖ C max. Indeed, the new reductions explore the structure of scheduling problems and can also lead to other interesting results. For example, using the framework of our reduction for P ‖ C max, Chen et al. [5] are able to prove the APX-hardness of the scheduling problem in which the matrix of job processing times P = ( p ij ) m × n is of rank 3, solving the open problem mentioned in [2].

Details

MFCS Conference 2012 Conference Paper

An Improved Approximation Scheme for Variable-Sized Bin Packing

  • Klaus Jansen
  • Stefan Erich Julius Kraft

Abstract The variable-sized bin packing problem (VBP) is a well-known generalization of the NP-hard bin packing problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an AFPTAS for VBP and BP with performance guarantee \(P(I) \leq (1+ \varepsilon )OPT(I) + O(\log^2(\frac{1}{\varepsilon }))\). The additive term is much smaller than the additive term of already known AFPTAS. The running time of the algorithm is \(O( \frac{1}{\varepsilon ^6} \log\left(\frac{1}{\varepsilon }\right) + \log\left(\frac{1}{\varepsilon }\right) n)\) for bin packing and \(O(\frac{1}{\varepsilon ^{7}} \log^2\left(\frac{1}{\varepsilon }\right) + \log\left(\frac{1}{\varepsilon }\right)\left(M+n\right))\) for variable-sized bin packing, which is an improvement to previously known algorithms.

Details

SODA Conference 2009 Conference Paper

Improved approximation algorithms for scheduling with fixed jobs

  • Florian Diedrich
  • Klaus Jansen

We study two closely related problems in non-preemptive scheduling of sequential jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. Both formulations have different applications, e. g. in turnaround scheduling or overlay computing. For both problems we contribute approximation algorithms with an improved ratio of 3/2 + ∊, respectively. For scheduling with fixed jobs, a lower bound of 3/2 on the approximation ratio has been obtained by Scharbrodt, Steger & Weisser; for scheduling with non-availability we provide the same lower bound. In total, our approximation ratio for both problems is essentially tight via suitable inapproximability results. We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to large gaps.

Details

MFCS Conference 2007 Conference Paper

New Approximability Results for 2-Dimensional Packing Problems

  • Klaus Jansen
  • Roberto Solis-Oba

Abstract The strip packing problem is to pack a set of rectangles into a strip of fixed width and minimum length. We present asymptotic polynomial time approximation schemes for this problem without and with 90 o rotations. The additive constant in the approximation ratios of both algorithms is 1, improving on the additive term in the approximation ratios of the algorithm by Kenyon and Rémila (for the problem without rotations) and Jansen and van Stee (for the problem with rotations), both of which have a larger additive constant O (1/ ε 2 ), ε > 0. The algorithms were derived from the study of the rectangle packing problem: Given a set R of rectangles with positive profits, the goal is to find and pack a maximum profit subset of R into a unit size square bin [0, 1] ×[0, 1]. We present algorithms that for any value ε > 0 find a subset R ′ ⊆ R of rectangles of total profit at least (1 − ε ) OPT, where OPT is the profit of an optimum solution, and pack them (either without rotations or with 90 o rotations) into the augmented bin [0, 1] ×[0, 1 + ε ].

Details

MFCS Conference 2005 Conference Paper

Packing Weighted Rectangles into a Square

  • Aleksei V. Fishkin
  • Olga Gerber
  • Klaus Jansen
  • Roberto Solis-Oba

Abstract We consider the problem of packing a set of weighted rectangles into a unit size square frame [0, 1] × [0, 1] so as to maximize the total weight of the packed rectangles. We present polynomial time approximation schemes (PTASs) that, for any ε >0, find (1 - ε )-approximate solutions for two special cases of the problem. In the first case we pack a set of squares whose weights are equal to their areas. In the second case we pack a set of weighted rectangles into an augmented square frame [0, 1 + 3 ε ] × [0, 1 + 3 ε ].

Details

MFCS Conference 2000 Conference Paper

Preemptive Scheduling on Dedicated Processors: Applications of Fractional Graph Coloring

  • Klaus Jansen
  • Lorant Porkolab

Abstract We study the problem of scheduling independent multiprocessor tasks, where for each task in addition to the processing time(s) there is a prespecified dedicated subset (or a family of alternative subsets) of processors which are required to process the task simultaneously. Focusing on problems where all required (alternative) subsets of processors have the same fixed cardinality, we present complexity results for computing preemptive schedules with minimum makespan closing the gap between computationally tractable and intractable instances. In particular, we show that for the dedicated version of the problem, optimal preemptive schedules of bi-processor tasks (i. e. tasks whose dedicated processor sets are all of cardinality two) can be computed in polynomial time. We give various extensions of this result including one to maximum lateness minimization with release times and due dates. All these results are based on a nice relation between preemptive scheduling and fractional coloring of graphs. In contrast to the positive results, we also prove that the problems of computing optimal preemptive schedules for three-processor tasks or for bi-processor tasks with (possible several) alternative modes are strongly NP-hard.

Details

MFCS Conference 1993 Conference Paper

On the Complexity of Scheduling Incompatible Jobs with Unit-Times

  • Hans L. Bodlaender
  • Klaus Jansen

Abstract We consider scheduling problems in a multiprocessor system with incompatibile jobs of unit-time length where two incompatible jobs can not be processed on the same machine. Given a deadline κ′ and a number of κ machines, the problem is to find a feasible assignment of the jobs to the machines. We prove the computational complexity of this scheduling problem restricted to different graph classes, arbitary and constant numbers κ and κ′.

Details