Source author record

Qilong Feng

Qilong Feng appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

preprint2022arXiv

New Approximation Algorithms for Fair $k$-median Problem

The fair $k$-median problem is one of the important clustering problems. The current best approximation ratio is 4.675 for this problem with 1-fair violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. As far as we know, there is no available approximation algorithm for the problem without any fair violation. In this paper, we consider the fair $k$-median problem in bounded doubling metrics and general metrics. We provide the first QPTAS for fair $k$-median problem in doubling metrics. Based on the split-tree decomposition of doubling metrics, we present a dynamic programming process to find the candidate centers, and apply min-cost max-flow method to deal with the assignment of clients. Especially, for overcoming the difficulties caused by the fair constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get part of the cost. For the fair $k$-median problem in general metrics, we present an approximation algorithm with ratio $O(\log k)$, which is based on the embedding of given space into tree metrics, and the dynamic programming method. Our two approximation algorithms for the fair $k$-median problem are the first results for the corresponding problems without any fair violation, respectively.

preprint2016arXiv

Parameterized Algorithms for the Maximum Agreement Forest Problem on Multiple Rooted Multifurcating Trees

The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of fixed-parameter algorithms. By taking advantage of a new branch-and-bound strategy, two parameterized algorithms, with running times $O(2.42^k m^3 n^4)$ and $O(2.74^k m^3 n^5)$, respectively, are presented for the hard version and the soft version of the problem, which correspond to two different biological meanings to the polytomies in multifurcating phylogenetic trees.

preprint2014arXiv

Algorithms for Maximum Agreement Forest of Multiple General Trees

The Maximum Agreement Forest (Maf) problem is a well-studied problem in evolutionary biology, which asks for a largest common subforest of a given collection of phylogenetic trees with identical leaf label-set. However, the previous work about the Maf problem are mainly on two binary phylogenetic trees or two general (i.e., binary and non-binary) phylogenetic trees. In this paper, we study the more general version of the problem: the Maf problem on multiple general phylogenetic trees. We present a parameterized algorithm of running time $O(3^k n^2m)$ and a 3-approximation algorithm for the Maf problem on multiple rooted general phylogenetic trees, and a parameterized algorithm of running time $O(4^k n^2m)$ and a 4-approximation algorithm for the Maf problem on multiple unrooted general phylogenetic trees. We also implement the parameterized algorithm and approximation algorithm for the Maf problem on multiple rooted general phylogenetic trees, and test them on simulated data and biological data.