Dan Alistarh,Giorgi Nadiradze,Amirmojtaba Sabour
Dan Alistarh
We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t ≥ 0 , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assu...
Ioannis Caragiannis,Panagiotis Kanellopoulos,Alexandros A Voudouris
Ioannis Caragiannis
Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but they a...
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...