output
20042026
most citedResearch Commentary on Recommendations with Side Information: A Survey and Research Directions

192 citations

Showing cs.DSShow all

12 papers · 1 filter

cs.DS2025

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Tsz Chiu Kwok, Zhewei Wei, Mingji Yang

We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system in sublinear time, with the goal of estimating for a given vector $t\in…

cs.DS2022★ 9 cited

(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics

Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu

Motivated by display advertising on the internet, the online stochastic matching problem is proposed by Feldman, Mehta, Mirrokni, and Muthukrishnan (FOCS 2009). Consider a stochast…

cs.DS2020

Generalized Sorting with Predictions

Pinyan Lu, Xuandi Ren, Enze Sun +1

Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…

cs.DS2020★ 10 cited

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit +1

We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour t…

cs.DS2020★ 5 cited

Fully Online Matching II: Beating Ranking and Water-filling

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu +1

Karp, Vazirani, and Vazirani (STOC 1990) initiated the study of online bipartite matching, which has held a central role in online algorithms ever since. Of particular importance a…

cs.DS2019

Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler

Zhengfeng Ji, Zhihan Jin, Pinyan Lu

The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically Boson…

cs.DS2019★ 4 cited

Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio

Minming Li, Pinyan Lu, Yuhao Yao +1

In this paper, we study the two-facility location game on a line with optional preference where the acceptable set of facilities for each agent could be different and an agent's co…

cs.DS2018★ 1 cited

-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial-Time Algorithm

Fabrizio Grandoni, Bundit Laekhanukit, Shi Li

In the Directed Steiner Tree (DST) problem we are given an -vertex directed edge-weighted graph, a root , and a collection of terminal nodes. Our goal is to find a minimu…

cs.DS2018★ 1 cited

On subexponential running times for approximating directed Steiner tree and related problems

Marek Cygan, Guy Kortsarz, Bundit Laekhanukit

This paper concerns proving almost tight (super-polynomial) running times, for achieving desired approximation ratios for various problems. To illustrate, the question we study, le…

cs.DS2017

Nearly Tight Bounds for Sandpile Transience on the Grid

David Durfee, Matthew Fahrbach, Yu Gao +1

We use techniques from the theory of electrical networks to give nearly tight bounds for the transience class of the Abelian sandpile model on the two-dimensional grid up to polylo…

cs.DS2015★ 2 cited

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Heng Guo, Pinyan Lu

We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almo…

cs.DS2011★ 15 cited

Correlation Decay up to Uniqueness in Spin Systems

Liang Li, Pinyan Lu, Yitong Yin

We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnet…