12 citations · 20 across the 13 of their papers we have counts for
17 papers
Parallel Greedy Spanners
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
A -spanner of a graph is a subgraph that -approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a spa…
Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang
Given an undirected unweighted graph on vertices and edges, a subgraph is a spanner of with stretch function $f: \mathbb{R}_+ \rightarrow \m…
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest -Subgraph and Other Problems
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg +1
We propose a new conjecture on hardness of low-degree -CSP's, and show that new hardness of approximation results for Densest -Subgraph and several other problems, including…
Query Complexity of the Metric Steiner Tree Problem
Yu Chen, Sanjeev Khanna, Zihan Tan
We study the query complexity of the metric Steiner Tree problem, where we are given an metric on a set of vertices along with a set of termina…
Near-Linear -Emulators for Planar Graphs
Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan
We study vertex sparsification for distances, in the setting of planar graphs with distortion: Given a planar graph (with edge weights) and a subset of terminal vertices, t…
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Yu Chen, Sanjeev Khanna, Zihan Tan
We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP…
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy, Zihan Tan
We consider the classical Minimum Crossing Number problem: given an -vertex graph , compute a drawing of in the plane, while minimizing the number of crossings between th…
Worst-Case Welfare of Item Pricing in the Tollbooth Problem
Zihan Tan, Yifeng Teng, Mingfei Zhao
We study the worst-case welfare of item pricing in the \emph{tollbooth problem}. The problem was first introduced by Guruswami et al, and is a special case of the combinatorial auc…
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph in the plane so as to minimize the number of cross…
On Packing Low-Diameter Spanning Trees
Julia Chuzhoy, Merav Parter, Zihan Tan
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every …
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …
Towards Tight(er) Bounds for the Excluded Grid Theorem
Julia Chuzhoy, Zihan Tan
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem sta…
Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship
Ioannis Caragiannis, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen +2
We study the truthful facility assignment problem, where a set of agents with private most-preferred points on a metric space are assigned to facilities that lie on the metric spac…
Robust Influence Maximization
Wei Chen, Tian Lin, Zihan Tan +2
In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding…
Comments on Cut-Set Bounds on Network Function Computation
Cupjin Huang, Zihan Tan, Shenghao Yang +1
A function computation problem in directed acyclic networks has been considered in the literature, where a sink node wants to compute a target function with the inputs generated at…
On the Inequalities of Projected Volumes and the Constructible Region
Zihan Tan, Liwei Zeng
We study the following geometry problem: given a dimensional vector , is there an object such that $\lo…
On the Meeting Time for Two Random Walks on a Regular Graph
Yizhen Zhang, Zihan Tan, Bhaskar Krishnamachari
We provide an analysis of the expected meeting time of two independent random walks on a regular graph. For 1-D circle and 2-D torus graphs, we show that the expected meeting time…