We study the q-adic assignment problem. We first give an O(n(q−1)/2))-approximation algorithm for the Koopmans--Beckman version of the problem, improving upon the result of Barvinok. Then, we introduce a new family of instances satisfying “tensor triangle inequalities” and give a constant factor approximation algorithm for them. We show that many classical optimization problems can be modeled by q-adic assignment problems from this family. Finally, we give several integrality gap examples for the natural LP relaxations of the problem. PubDate: Tue, 14 Nov 2017 00:00:00 GMT

We give a variant of the pairing heaps that achieves the following amortized costs: O(1) per find-min and insert, O(log log n) per decrease-key and meld, O(log n) per delete-min; where n is the number of elements in the resulting heap on which the operation is performed. These bounds are the best known for any self-adjusting heap and match two lower bounds, one established by Fredman and the other by Iacono and Özkan, for a family of self-adjusting heaps that generalizes the pairing heaps but do not include our variant. PubDate: Tue, 14 Nov 2017 00:00:00 GMT

Divide-and-conquer recurrences of the form f(n) = f (⌊ &fracn2;⌋ ) + f ( ⌈ &fracn2;⌉ ) + g(n) (n⩾ 2), with g(n) and f(1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f(n) = n P(log2n) − Q(n) under an optimum (iff) condition on g(n). This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. PubDate: Wed, 25 Oct 2017 00:00:00 GMT

In the network activation problem, each edge in a graph is associated with an activation function that decides whether the edge is activated from weights assigned to its end nodes. The feasible solutions of the problem are node weights such that the activated edges form graphs of required connectivity, and the objective is to find a feasible solution minimizing its total weight. In this article, we consider a prize-collecting version of the network activation problem and present the first nontrivial approximation algorithms. Our algorithms are based on a new linear programming relaxation of the problem. They round optimal solutions for the relaxation by repeatedly computing node weights activating subgraphs, called spiders, which are known to be useful for approximating the network activation problem. PubDate: Wed, 25 Oct 2017 00:00:00 GMT

Consider a forest that evolves via link operations that make the root of one tree the child of a node in another tree. Intermixed with link operations are nca operations, which return the nearest common ancestor of two given nodes when such exists. This article shows that a sequence of m such nca and link operations on a forest of n nodes can be processed online in time O(mα (m,n)+n). This was previously known only for a restricted type of link operation. The special case where a link only extends a tree by adding a new leaf occurs in Edmonds’ algorithm for finding a maximum weight matching on a general graph. PubDate: Tue, 19 Sep 2017 00:00:00 GMT

A skew-symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a skew-symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D′=(V,A \ (X ∪ σ(X)). PubDate: Tue, 19 Sep 2017 00:00:00 GMT

Abstract: Andreas Björklund, Petteri Kaski, Łukasz Kowalik

Vassilevska and Williams (STOC’09) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP’09), and Björklund et al. (ESA’09), via nst/2+O(1)-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG’10) showed that these problems have Ω(n⌊ st/2⌋) and Ω(n⌊ k/2⌋) lower bounds when counting by color coding. Here, we show that one can do better—we show that the “meet-in-the-middle” exponent st/2 can be beaten and give an algorithm that counts in time n0.45470382st+O(1) for t a multiple of three. PubDate: Tue, 19 Sep 2017 00:00:00 GMT