Stefano Leucci,Chih-Hung Liu
Stefano Leucci
We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly-ordered collection of n elements by only performing unreliab...
Sayan Bandyapadhyay
Sayan Bandyapadhyay
The Non-Uniform k-center (NUkC) problem has recently been formulated by Chakrabarty et al. [ICALP, 2016; ACM Trans Algorithms 16(4):46:1-46:19, 2020] as a generalization of the classical k-center clustering problem. In NUkC, given a set of ...
Susanne Albers,Arindam Khan,Leon Ladewig
Susanne Albers
Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) ...
Susanne Albers,Maximilian Janke
Susanne Albers
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to m identical parallel machines so as to minimize the maximum completion time of any job. Already in the 19...
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs [0.03%]
亚指数时间算法用于寻找大的诱导稀疏子图
Jana Novotná,Karolina Okrasa,Michał Pilipczuk et al.
Jana Novotná et al.
Let C and D be hereditary graph classes. Consider the following problem: given a graph G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C . We prove that it can be solved in 2 o ( n ) ...
Marco Bressan
Marco Bressan
Given a k-node pattern graph H and an n-node host graph G, the subgraph counting problem asks to compute the number of copies of H in G. In this work we address the following question: can we count the copies of H faster if G is sparse? We ...
Improved Online Algorithms for Knapsack and GAP in the Random Order Model [0.03%]
随机模型中背包问题和GAP的改进在线算法
Susanne Albers,Arindam Khan,Leon Ladewig
Susanne Albers
The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the onlin...
Britta Dorn,Ronald de Haan,Ildikó Schlotter
Britta Dorn
We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion gua...
Robert Ganian,Sebastian Ordyniak
Robert Ganian
This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in ...
Jurek Czyzowicz,Dariusz Dereniowski,Andrzej Pelc
Jurek Czyzowicz
A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid Z × Z . Some cells of the grid are full (contain a brick) and others are emp...