Recent zbMATH articles by "Jansen, Klaus"https://zbmath.org/atom/ai/jansen.klaus2024-03-13T18:33:02.981707ZWerkzeugRankings of graphshttps://zbmath.org/1528.682742024-03-13T18:33:02.981707Z"Bodlaender, H. L."https://zbmath.org/authors/?q=ai:bodlaender.hans-l"Deogun, J. S."https://zbmath.org/authors/?q=ai:deogun.jitender-s"Jansen, K."https://zbmath.org/authors/?q=ai:jansen.klaus"Kloks, T."https://zbmath.org/authors/?q=ai:kloks.ton"Kratsch, D."https://zbmath.org/authors/?q=ai:kratsch.dieter"Müller, H."https://zbmath.org/authors/?q=ai:muller.haiko"Tuza, Zs."https://zbmath.org/authors/?q=ai:tuza.zsoltSummary: A vertex (edge) coloring \(c :V \rightarrow \{1, 2, \ldots, t\}\) (\(c':E \rightarrow \{1, 2, \ldots, t\}\)) of a graph \(G=(V, E)\) is a vertex (edge) \(t\)-\textit{ranking} if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The \textit{vertex ranking number} \(\chi _r (G)\) (\textit{edge ranking number} \(\chi '_r (G))\) is the smallest value of \(t\) such that \(G\) has a vertex (edge) \(t\)-ranking. In this paper we study the algorithmic complexity of the \textsc{vertex ranking} and \textsc{edge ranking} problems. Among others it is shown that \(\chi_r (G)\) can be computed in polynomial time when restricted to graphs with treewidth at most \(k\) for any fixed \(k\). We characterize those graphs where the vertex ranking number \(\chi_r\) and the chromatic number \(\chi\) coincide on all induced subgraphs, show that \(\chi_r (G)= \chi (G)\) implies \(\chi(G)=\omega(G)\) (largest clique size) and give a formula for \(\chi '_r (K_n)\).
For the entire collection see [Zbl 0813.68031].Approximation results for makespan minimization with budgeted uncertaintyhttps://zbmath.org/1528.901042024-03-13T18:33:02.981707Z"Bougeret, Marin"https://zbmath.org/authors/?q=ai:bougeret.marin"Jansen, Klaus"https://zbmath.org/authors/?q=ai:jansen.klaus"Poss, Michael"https://zbmath.org/authors/?q=ai:poss.michael"Rohwedder, Lars"https://zbmath.org/authors/?q=ai:rohwedder.larsSummary: We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to
\textit{D. Bertsimas} and \textit{M. Sim} [Math. Program. 98, No. 1--3 (B), 49--71 (2003; Zbl 1082.90067)],
once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of \(2-\epsilon\) for the case of unrelated machines.
For the entire collection see [Zbl 1435.68018].