10 papers
Polynomial Kernels for Interval Completion
Zimo Sheng, Tian Bai, Mingyu xiao
An interval graph is the intersection graph of a family of intervals on the real line. \textsc{Interval Completion} asks whether a given graph can be transformed into an interval g…
Feedback Set Problems on Bounded-Degree (Planar) Graphs
Tian Bai, Yixin Cao, Mingyu Xiao
The feedback set problems are about removing the minimum number of vertices or edges from a graph to break all its cycles. Much effort has gone into understanding their complexity…
On the Leaky Private Information Retrieval with Side Information
Yingying Huangfu, Tian Bai
This paper investigates the problem of Leaky Private Information Retrieval with Side Information (L-PIR-SI), providing a fundamental characterization of the trade-off among leaky p…
Optimal Stopping with a Predicted Prior
Tian Bai, Zhiyi Huang, Chui Shan Lee +1
There are two major models of value uncertainty in the optimal stopping literature: the secretary model, which assumes no prior knowledge, and the prophet inequality model, which a…
Contracting with a Mechanism Designer
Tian Bai, Yiding Feng, Yaohao Liu +2
This paper explores the economic interactions within modern crowdsourcing markets. In these markets, employers issue requests for tasks, platforms facilitate the recruitment of cro…
An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
Tian Bai
In the Feedback Arc Set in Tournaments (Subset-FAST) problem, we are given a tournament and a positive integer , and the objective is to determine whether there exists an ar…
Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism Design
Mengfan Ma, Mingyu Xiao, Tian Bai +1
In the one-dimensional facility assignment problem, m facilities and n agents are positioned along the real line. Each agent will be assigned to a single facility to receive servic…
A Cooperative Statistical Approach for Abnormal Node Detection with Adversary Resistance
Yingying Huangfu, Tian Bai
Distinguishing abnormal nodes from those with normal packet loss in clusters helps reduce the loss of clustered network resources. The detection performance of existing detection s…
Breaking the Barrier for Subset Feedback Vertex Set in Chordal Graphs
Tian Bai, Mingyu Xiao
The Subset Feedback Vertex Set problem (SFVS), to delete vertices from a given graph such that any vertex in a vertex subset (called a terminal set) is not in a cycle in the re…
Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
Mengfan Ma, Mingyu Xiao, Tian Bai +1
The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility.…