This paper presents a new combinatorial optimisation task, the Subset Sum Matching Problem (SSMP), which is an abstraction of common financial applications such as trades reconciliation. We present three algorithms, two suboptimal and one optimal, to solve this problem. We also generate a benchmark to cover different instances of SSMP varying in complexity, and carry out an experimental evaluation to assess the performance of the approaches.

In this work we consider a new interpretation of fairness in decision making problems. Building upon existing fairness formulations, we focus on how to reason over fairness from a temporal perspective, taking into account the fairness of a history of past decisions. After introducing the concept of temporal fairness, we propose three approaches that incorporate temporal fairness in decision making problems formulated as optimization problems. We present a qualitative evaluation of our approach in four different domains and compare the solutions against a baseline approach that does not consider the temporal aspect of fairness.

The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S ⊆ V of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of DSG via the lens of supermodularity. For this we consider the densest supermodular subset problem (DSS): given a non-negative supermodular function f : 2V → ℝ+, maximize f(S)/|S|. For DSG we describe a simple flow-based algorithm that outputs a (1–∊)-approximation in deterministic Õ(m/∊) time where m is the number of edges. Our algorithm is the first to have a near-linear dependence on m and 1/∊ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed DSG. Greedy peeling algorithms have been very popular for DSG and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for DSS and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al. [12] developed an iterative peeling algorithm for DSG which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a (1–∊)-approximation for any supermodular function f; the key to our proof is to consider an LP formulation that is derived via the Lovász extension of a supermodular function. For DSG the bound on the number of iterations we prove is where Δ is the maximum degree and λ∗ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the 2-approximation for densest-at-least-k subgraph [37] extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of DSS to maximize f(S)/g(|S|) for a concave function g.

We introduce new dynamic set intersection data structures, which we call 2-3 cuckoo filters and hash tables. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each item, instead of one out of two, ensuring that any item in an intersection of two structures will have at least one common location in both structures. We demonstrate the utility of these structures by using them in improved algorithms for listing triangles and answering set intersection queries in internal or external memory. For a graph G of n vertices and m edges, our internal-memory triangle listing algorithm runs in O(m⌈(α(G)log w)/w⌉ + k) expected time, where α(G) is the arboricity of G, w is the number of bits in a machine word, and k is the number of output triangles. Our external-memory algorithm uses O(sort(n,α(G))+ sort(m⌈(α(G)log w)/w⌉) + sort(k)) expected number of I/Os.

We provide an efficient algorithm for determining how a road network has evolved over time, given two snapshot instances from different dates. To allow for such determinations across different databases and even against hand-drawn maps, we take a strictly topological approach in this paper, so that we compare road networks based strictly on graph-theoretic properties. Given two road networks of same region from two different dates, our approach allows one to match road network portions that remain intact and also point out added or removed portions. We analyze our algorithm both theoretically, showing that it runs in polynomial time for non-degenerate road networks even though a related problem is NP-complete, and experimentally, using dated road networks from the TIGER/Line archive of the U.S. Census Bureau.

Volunteer Computing (VC) uses the computational resources of volunteers with Internet-connected personal computers to address fundamental problems in science. Docking Home (D@H) is a VC project targeting drug discovery through high throughput docking simulations i.e., by docking small molecules (ligands) into target proteins associated to diseases. Currently there are more than 27,000 volunteers (and 70,000 computers) worldwide supporting D@H. Similar to national trends in STEM fields, in general, the huge majority of volunteers engaged in VC projects, and in D@H in particular, are Caucasian males. This paper aims to characterize the current VC community supporting D@H and uses the information to define strategies that can help attract and retain female and ethnic minority volunteers.