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

Zhihan Gao

Zhihan Gao contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmscond-mat.mtrl-sci

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
2topics
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)

preprint2015arXiv

On the metric s-t path Traveling Salesman Problem

We study the metric $s$-$t$ path Traveling Salesman Problem (TSP). [An, Kleinberg, and Shmoys, STOC 2012] improved on the long standing $\frac{5}{3}$-approximation factor and presented an algorithm that achieves an approximation factor of $\frac{1+\sqrt{5}}{2}\approx1.61803$. Later [Sebő, IPCO 2013] further improved the approximation factor to $\frac{8}{5}$. We present a simple, self-contained analysis that unifies both results; our main contribution is a \emph{unified correction vector}. We compare two different linear programming (LP) relaxations of the $s$-$t$ path TSP, namely, the path version of the Held-Karp LP relaxation for TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum-cost of integral solutions of the two LPs are within a factor of $\frac{3}{2}$ of each other. We prove that a half-integral solution of the stronger LP-relaxation of cost $c$ can be rounded to an integral solution of cost at most $\frac{3}{2}c$. Additionally, we give a bad instance that presents obstructions to two obvious methods that aim for an approximation factor of $\frac{3}{2}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy

We study the ATSP (Asymmetric Traveling Salesman Problem), and our focus is on negative results in the framework of the Sherali-Adams (SA) Lift and Project method. Our main result pertains to the standard LP (linear programming) relaxation of ATSP, due to Dantzig, Fulkerson, and Johnson. For any fixed integer $t\geq 0$ and small $ε$, $0<ε\ll{1}$, there exists a digraph $G$ on $ν=ν(t,ε)=O(t/ε)$ vertices such that the integrality ratio for level~$t$ of the SA system starting with the standard LP on $G$ is $\ge 1+\frac{1-ε}{2t+3} \approx \frac43, \frac65, \frac87, \dots$. Thus, in terms of the input size, the result holds for any $t = 0,1,\dots,Θ(ν)$ levels. Our key contribution is to identify a structural property of digraphs that allows us to construct fractional feasible solutions for any level~$t$ of the SA system starting from the standard~LP. Our hard instances are simple and satisfy the structural property. There is a further relaxation of the standard LP called the balanced LP, and our methods simplify considerably when the starting LP for the SA system is the balanced~LP; in particular, the relevant structural property (of digraphs) simplifies such that it is satisfied by the digraphs given by the well-known construction of Charikar, Goemans and Karloff (CGK). Consequently, the CGK digraphs serve as hard instances, and we obtain an integrality ratio of $1 +\frac{1-ε}{t+1}$ for any level~$t$ of the SA system, where $0<ε\ll{1}$ and the number of vertices is $ν(t,ε)=O((t/ε)^{(t/ε)})$. Also, our results for the standard~LP extend to the Path-ATSP (find a min cost Hamiltonian dipath from a given source vertex to a given sink vertex).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Ultrafast Terahertz Probe of Transient Evolution of Charged and Neutral Phase of Photoexcited Electron-hole Gas in Monolayer Semiconductor

We investigate the dynamical formation of excitons from photoexcited electron-hole plasma and its subsequent decay dynamics in monolayer MoS2 grown by chemical vapor deposition using ultrafast pump and terahertz probe spectroscopy. Different photoexcited electron-hole states are resolved based on their distinct responses to THz photon and decay lifetime. The observed transient THz transmission can be fit with two decay components: a fast component with decay lifetime of 20 ps, which is attributed to exciton life time including the exciton formation and subsequent intraexciton relaxation; a slow component with extremely long decay lifetime of several ns due to either localized exciton state or a long live dark exciton state which is uncovered for the first time. The relaxation dynamics is further verified by temperature and pump fluence dependent studies of the decay time constants.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximating Minimum-Cost Connected T-Joins

We design and analyse approximation algorithms for the minimum-cost connected T-join problem: given an undirected graph G = (V;E) with nonnegative costs on the edges, and a subset of nodes T, find (if it exists) a spanning connected subgraph H of minimum cost such that every node in T has odd degree and every node not in T has even degree; H may have multiple copies of any edge of G. Two well-known special cases are the TSP (|T| = 0) and the s-t path TSP (|T| = 2). Recently, An, Kleinberg, and Shmoys [STOC 2012] improved on the long-standing 5/3-approximation guarantee for the latter problem and presented an algorithm based on LP rounding that achieves an approximation guarantee of (1+sqrt(5))/2 < 1.6181. We show that the methods of An et al. extend to the minimum-cost connected T-join problem. They presented a new proof for a 5/3-approximation guarantee for the s-t path TSP; their proof extends easily to the minimum-cost connected T-join problem. Next, we improve on the approximation guarantee of 5/3 by extending their LP-rounding algorithm to get an approximation guarantee of 13/8 = 1.625 for all |T| >= 4. Finally, we focus on the prize-collecting version of the problem, and present a primal-dual algorithm that is &#34;Lagrangian multiplier preserving&#34; and that achieves an approximation guarantee 3 - 2/(|T|-1) when |T| >= 4. Our primal-dual algorithm is a generalization of the known primal-dual 2-approximation for the prize-collecting s-t path TSP. Furthermore, we show that our analysis is tight by presenting instances with |T| >= 4 such that the cost of the solution found by the algorithm is exactly 3 - 2/(|T|-1) times the cost of the constructed dual solution.

0 citations0 reviewsNo code linkedOpen access