Danny Hermelin | DeepAI

DeepAI AI Chat

Featured Co-authors

Rolf Niedermeier
71 publications
Michał Pilipczuk
62 publications
Marcin Pilipczuk
51 publications
Karl Bringmann
49 publications
Hendrik Molter
34 publications
Matthias Mnich
28 publications
Manuel Sorge
28 publications
Amir Abboud
27 publications
Jiehua Chen
27 publications
Till Fluschnik
23 publications
George B. Mertzios
20 publications

∙ 08/24/2023

No Polynomial Kernels for Knapsack

This paper focuses on kernelization algorithms for the fundamental Knaps...

0 Klaus Heeger, et al. ∙

∙ 06/26/2022

Hardness of Interval Scheduling on Unrelated Machines

We provide new (parameterized) computational hardness results for Interv...

0 Danny Hermelin, et al. ∙

∙ 02/14/2022

Single Machine Weighted Number of Tardy Jobs Minimization With Small Weights

In this paper we prove new results concerning pseudo-polynomial time alg...

0 Danny Hermelin, et al. ∙

∙ 12/27/2021

Equitable Scheduling for the Total Completion Time Objective

We investigate a novel scheduling problem where we have n clients, each ...

0 Danny Hermelin, et al. ∙

∙ 12/12/2021

Temporal Unit Interval Independent Sets

Temporal graphs have been recently introduced to model changes to a give...

0 Danny Hermelin, et al. ∙

∙ 10/07/2021

Polynomial Turing Kernels for Clique with an Optimal Number of Queries

A polynomial Turing kernel for some parameterized problem P is a polynom...

0 Till Fluschnik, et al. ∙

∙ 10/09/2020

Equitable Scheduling on a Single Machine

We introduce a natural but seemingly yet unstudied generalization of the...

0 Klaus Heeger, et al. ∙

∙ 07/02/2020

Approximating Sparse Quadratic Programs

Given a matrix A ∈ℝ^n× n, we consider the problem of maximizing x^TAx su...

0 Danny Hermelin, et al. ∙

∙ 05/31/2020

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

We present a data structure that in a dynamic graph of treedepth at most...

0 Jiehua Chen, et al. ∙

∙ 03/16/2020

Scheduling Lower Bounds via AND Subset Sum

Given N instances (X_1,t_1),...,(X_N,t_N) of Subset Sum, the AND Subset ...

0 Amir Abboud, et al. ∙

∙ 03/16/2020

Faster Minimization of Tardy Processing Time on a Single Machine

This paper is concerned with the 1||∑ p_jU_j problem, the problem of min...

0 Karl Bringmann, et al. ∙

∙ 02/18/2020

Computing the k Densest Subgraphs of a Graph

Computing cohesive subgraphs is a central problem in graph theory. While...

0 Riccardo Dondi, et al. ∙

∙ 11/27/2019

Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs

The 1|B,r_j|∑ w_jU_j scheduling problem takes as input a batch setup tim...

0 Danny Hermelin, et al. ∙

∙ 07/24/2018

A Note on Clustering Aggregation

We consider the clustering aggregation problem in which we are given a s...

0 Jiehua Chen, et al. ∙

∙ 07/17/2018

On Computing Centroids According to the p-Norms of Hamming Distance Vectors

In this paper we consider the p-Norm Hamming Centroid problem which asks...

0 Jiehua Chen, et al. ∙

∙ 02/22/2018

The Clever Shopper Problem

We investigate a variant of the so-called "Internet Shopping Problem" in...

0 Laurent Bulteau, et al. ∙

∙ 09/18/2017

New Algorithms for Minimizing the Weighted Number of Tardy Jobs On a Single Machine

In this paper we study the classical single machine scheduling problem w...

0 Danny Hermelin, et al. ∙

∙ 07/13/2017

How hard is it to satisfy (almost) all roommates?

The classical Stable Roommates problem (which is a non-bipartite general...

0 Jiehua Chen, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world