BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Arash Haddadan

Arash Haddadan contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete Mathematicscs.CYSocial and Information Networks

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2022arXiv

A Markov Decision Process Framework for Efficient and Implementable Contact Tracing and Isolation

Efficient contact tracing and isolation is an effective strategy to control epidemics. It was used effectively during the Ebola epidemic and successfully implemented in several parts of the world during the ongoing COVID-19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine -- the budget is limited for socioeconomic reasons. In this paper, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while asking a limited number of people to quarantine. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NP-Hard; as a result, we develop an LP-based approximation algorithm. Though this algorithm directly solves MinExposed, it is often impractical in the real world due to information constraints. To this end, we develop a greedy approach based on insights from the analysis of the previous algorithm, which we show is more interpretable. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network. This makes the heuristic implementable in practice and is an important consideration. Finally, we carry out experiments on simulations of the MDP run on real-world networks, and show how the algorithms can help in bending the epidemic curve while limiting the number of isolated individuals. Our experimental results demonstrate that the greedy algorithm and its variants are especially effective, robust, and practical in a variety of realistic scenarios, such as when the contact graph and specific transmission probabilities are not known. All code can be found in our GitHub repository: https://github.com/gzli929/ContactTracing.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Approximation Algorithms for Flexible Graph Connectivity

We present approximation algorithms for several network design problems in the model of Flexible Graph Connectivity (Adjiashvili, Hommelsheim and Mühlenthaler, "Flexible Graph Connectivity", Math. Program. pp. 1-33 (2021), and IPCO 2020: pp. 13-26). Let $k\geq 1$, $p\geq 1$ and $q\geq 0$ be integers. In an instance of the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, we have an undirected connected graph $G = (V,E)$, a partition of $E$ into a set of safe edges $S$ and a set of unsafe edges $U$, and nonnegative costs $c: E\to\Re$ on the edges. A subset $F \subseteq E$ of edges is feasible for the $(p,q)$-FGC problem if for any subset $F'$ of unsafe edges with $|F'|\leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The algorithmic goal is to find a feasible solution $F$ that minimizes $c(F) = \sum_{e \in F} c_e$. We present a simple $2$-approximation algorithm for the $(1,1)$-FGC problem via a reduction to the minimum-cost rooted $2$-arborescence problem. This improves on the $2.527$-approximation algorithm of Adjiashvili et al. Our $2$-approximation algorithm for the $(1,1)$-FGC problem extends to a $(k+1)$-approximation algorithm for the $(1,k)$-FGC problem. We present a $4$-approximation algorithm for the $(p,1)$-FGC problem, and an $O(q\log|V|)$-approximation algorithm for the $(p,q)$-FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted $(1,1)$-FGC problem by presenting a $16/11$-approximation algorithm. The $(p,q)$-FGC problem is related to the well-known Capacitated $k$-Connected Subgraph problem (denoted Cap-k-ECSS) that arises in the area of Capacitated Network Design. We give a $\min(k,2 u_{max})$-approximation algorithm for the Cap-k-ECSS problem, where $u_{max}$ denotes the maximum capacity of an edge.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a $θ$-cyclic point: $x_e \in \{0,θ, 1-θ, 1\}$, where the support graph is subcubic and each vertex is incident to at least one edge with $x$-value 1. Such points are sufficient to resolve TSP in general. For these points, we construct a convex combination of tours in which we can reduce the usage of edges with $x$-value 1 from the $\frac{3}{2}$ of Christofides algorithm to $\frac{3}{2}-\fracθ{10}$ while keeping the usage of edges with fractional $x$-value the same as Christofides algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP: In the case when the objective function of the subtour elimination relaxation is minimized by a $\frac{2}{3}$-uniform point: $x_e \in \{0, \frac{2}{3}\}$, we give a $\frac{17}{12}$-approximation algorithm for TSP. For such points, this lands us halfway between the approximation ratios of $\frac{3}{2}$ of Christofides algorithm and $\frac{4}{3}$ implied by the famous "four-thirds conjecture".

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fractional Decomposition Tree Algorithm: A tool for studying the integrality gap of Integer Programs

We present a new algorithm, Fractional Decomposition Tree (FDT) for finding a feasible solution for an integer program (IP) where all variables are binary. FDT runs in polynomial time and is guaranteed to find a feasible integer solution provided the integrality gap is bounded. The algorithm gives a construction for Carr and Vempala's theorem that any feasible solution to the IP's linear-programming relaxation, when scaled by the instance integrality gap, dominates a convex combination of feasible solutions. FDT is also a tool for studying the integrality gap of IP formulations. We demonstrate that with experiments studying the integrality gap of two problems: optimally augmenting a tree to a 2-edge-connected graph and finding a minimum-cost 2-edge-connected multi-subgraph (2EC). We also give a simplified algorithm, Dom2IP, that more quickly determines if an instance has an unbounded integrality gap. We show that FDT's speed and approximation quality compare well to that of feasibility pump on moderate-sized instances of the vertex cover problem. For a particular set of hard-to-decompose fractional 2EC solutions, FDT always gave a better integer solution than the best previous approximation algorithm (Christofides).

0 citations0 reviewsNo code linkedOpen access