Search

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., Comment: Paper accepted at ECAI 2024. This is an extended version that includes Supplementary Material

Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum average degree). Both of these problems can be solved in polynomial time. Veldt, Benson, and Kleinberg [VBK21] introduced the generalized $p$-mean densest subgraph problem which captures the maxcore problem when $p=-\infty$ and the densest subgraph problem when $p=1$. They observed that the objective leads to a supermodular function when $p \ge 1$ and hence can be solved in polynomial time; for this case, they also developed a simple greedy peeling algorithm with a bounded approximation ratio. In this paper, we make several contributions. First, we prove that for any $p \in (-\frac{1}{8}, 0) \cup (0, \frac{1}{4})$ the problem is NP-Hard and for any $p \in (-3,0) \cup (0,1)$ the weighted version of the problem is NP-Hard, partly resolving a question left open in [VBK21]. Second, we describe two simple $1/2$-approximation algorithms for all $p < 1$, and show that our analysis of these algorithms is tight. For $p > 1$ we develop a fast near-linear time implementation of the greedy peeling algorithm from [VBK21]. This allows us to plug it into the iterative peeling algorithm that was shown to converge to an optimum solution [CQT22]. We demonstrate the efficacy of our algorithms by running extensive experiments on large graphs. Together, our results provide a comprehensive understanding of the complexity of the $p$-mean densest subgraph problem and lead to fast and provably good algorithms for the full range of $p$.

We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing-ST). We solve the underlying LP to within a $(1+\epsilon)$ approximation factor in near-linear time via the multiplicative weight update (MWU) technique. This yields, in particular, a near-linear time algorithm that outputs an estimate $B$ such that $B \le B^* \le \lceil (1+\epsilon)B \rceil +1$ where $B^*$ is the minimum-degree of a spanning tree of a given graph. To round the fractional solution, in our main technical contribution, we describe a fast near-linear time implementation of swap-rounding in the spanning tree polytope of a graph. The fractional solution can also be used to sparsify the input graph that can in turn be used to speed up existing combinatorial algorithms. Together, these ideas lead to significantly faster approximation algorithms than known before for the two problems of interest. In addition, a fast algorithm for swap rounding in the graphic matroid is a generic tool that has other applications, including to TSP and submodular function maximization., Comment: Updated to reflect overlap in results with arXiv:1811.07464

We consider approximation algorithms for packing integer programs (PIPs) of the form $\max\{\langle c, x\rangle : Ax \le b, x \in \{0,1\}^n\}$ where $c$, $A$, and $b$ are nonnegative. We let $W = \min_{i,j} b_i / A_{i,j}$ denote the width of $A$ which is at least $1$. Previous work by Bansal et al. \cite{bansal-sparse} obtained an $\Omega(\frac{1}{\Delta_0^{1/\lfloor W \rfloor}})$-approximation ratio where $\Delta_0$ is the maximum number of nonzeroes in any column of $A$ (in other words the $\ell_0$-column sparsity of $A$). They raised the question of obtaining approximation ratios based on the $\ell_1$-column sparsity of $A$ (denoted by $\Delta_1$) which can be much smaller than $\Delta_0$. Motivated by recent work on covering integer programs (CIPs) \cite{cq,chs-16} we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. \cite{bansal-sparse} (but with a twist), yield approximation ratios for PIPs based on $\Delta_1$. First, following an integrality gap example from \cite{bansal-sparse}, we observe that the case of $W=1$ is as hard as maximum independent set even when $\Delta_1 \le 2$. In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width $W = 1 + \epsilon$ where $\epsilon \in (0,1]$, we obtain an $\Omega(\epsilon^2/\Delta_1)$-approximation. In the large width regime, when $W \ge 2$, we obtain an $\Omega((\frac{1}{1 + \Delta_1/W})^{1/(W-1)})$-approximation. We also obtain a $(1-\epsilon)$-approximation when $W = \Omega(\frac{\log (\Delta_1/\epsilon)}{\epsilon^2})$., Comment: To appear in IPCO 2019

Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points have angular orientations in addition to their positions., Comment: 15 pages, 12 figures, to be presented at CCCG18

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.