Maciej Pacut's paper "An Optimal Algorithm for Online Multiple Knapsack" was accepted to ICALP track A.
Abstract
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of n bins (knapsacks) of equal size. The gain of an algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain.
So far, for this natural problem, the best solution was the 0.5-competitive algorithm FirstFit (the result holds for any n ≥ 2). We present the first algorithm that beats this ratio, achieving the competitive ratio of 1/(1 + ln(2)) - O(1/n) ≈ 0.5906 - O(1/n).
Ami Paz's paper "The Topology of Local Computing in Networks" was accepted to ICALP track B.
Abstract
We continue a long line of work on modeling distributed computing in a way enabling the use of formal methods. This is done by describing the possible states of the system using mathematical objects called simplicial complexes. One considerable challenge in applying these methods comes from the presence of identifiers assigned to the processing units, which yields simplicial complexes whose sizes grow exponentially with the size of the system.
However, many of the network problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present local protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of these local protocol complexes, we reformulate the celebrated lower bound of log* n rounds for 3-coloring the n-node ring in the algebraic topology framework.
This is a joint work with Pierre Fraigniaud.
