期刊： ACM TRANSACTIONS ON ALGORITHMS, 2021; 17 (1)
We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint functio......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (3)
It was recently found that there are very close connections between the existence of additive spanners (sub-graphs where all distances are preserved u......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (2)
We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the priz......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (1)
Often in a scheduling problem, there is uncertainty about the jobs to be processed. The issue of uncertainty regarding the machines has been much less......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (1)
This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2020; 16 (1)
The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Delta. In this article, we explore......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2019; 15 (1)
We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2019; 15 (3)
We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighte......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (1)
We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O(m root n......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (1)
We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow-......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (1)
We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find the shortest tour that visits each of a ......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (4)
We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of item......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (4)
We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in ......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (2)
We study the problem of two-dimensional orthogonal range counting with additive error. Given a set P of n points drawn from an n x n grid and an error......
期刊： ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (2)
We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algoritlun on the oblivious matching problem where nodes ......
