Zobrazeno 1 - 10
of 68
pro vyhledávání: '"Heeger, Klaus"'
Fair resource allocation is undoubtedly a crucial factor in customer satisfaction in several scheduling scenarios. This is especially apparent in repetitive scheduling models where the same set of clients repeatedly submits jobs on a daily basis. In
Externí odkaz:
http://arxiv.org/abs/2407.03987
Autor:
Heeger, Klaus, Molter, Hendrik
In this work, we study the computational (parameterized) complexity of $P \mid r_j, p_j=p \mid \sum_j w_j U_j$. Here, we are given $m$ identical parallel machines and $n$ jobs with equal processing time, each characterized by a release date, a due da
Externí odkaz:
http://arxiv.org/abs/2404.14208
This paper resolves a long-standing open question in bicriteria scheduling regarding the complexity of a single machine scheduling problem which combines the number of tardy jobs and the maximal tardiness criteria. We use the lexicographic approach w
Externí odkaz:
http://arxiv.org/abs/2404.02784
We study the computational complexity of several polynomial-time-solvable graph problems parameterized by vertex integrity, a measure of a graph's vulnerability to vertex removal in terms of connectivity. Vertex integrity is the smallest number $\iot
Externí odkaz:
http://arxiv.org/abs/2403.01839
Autor:
Heeger, Klaus, Hermelin, Danny
We consider the $1||\sum w_J U_j$ problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both
Externí odkaz:
http://arxiv.org/abs/2401.01740
This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-speci
Externí odkaz:
http://arxiv.org/abs/2308.12593
We provide a general framework to exclude parameterized running times of the form $O(\ell^\beta+ n^\gamma)$ for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-com
Externí odkaz:
http://arxiv.org/abs/2301.00797
Focusing on Stable Roommates (SR) instances, we contribute to the toolbox for conducting experiments for stable matching problems. We introduce a polynomial-time computable pseudometric to measure the similarity of SR instances, analyze its propertie
Externí odkaz:
http://arxiv.org/abs/2208.04041
When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unst
Externí odkaz:
http://arxiv.org/abs/2208.01563
We study stable matching problems where agents have multilayer preferences: There are $\ell$ layers each consisting of one preference relation for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, establishing
Externí odkaz:
http://arxiv.org/abs/2205.07550