Bingkai Lin

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Hardness and fixed parameter tractability for pinwheel scheduling problems	2026-10-01	Paper
On average baby PIH and its applications	2026-06-24	Paper
Hardness and fixed parameter tractability for pinwheel scheduling problems Theoretical Computer Science	2026-06-15	Paper
Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH	2026-01-14	Paper
Parameterized inapproximability hypothesis under ETH Journal of the ACM	2025-11-27	Paper
Improved hardness of approximating k-clique under ETH	2025-08-15	Paper
The constant inapproximability of the parameterized dominating set problem	2025-08-06	Paper
FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set	2025-07-24	Paper
On lower bounds of approximating parameterized k-clique	2024-06-24	Paper
Constant approximating Parameterized \(k\)-\textsc{SetCover} is W[2]-hard	2024-05-14	Paper
Constant approximating k-clique is w[1]-hard Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Parameterized Intractability of Even Set and Shortest Vector Problem Journal of the ACM	2022-12-08	Paper
A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem (available as arXiv preprint)	2022-07-21	Paper
A nearly 5/3-approximation FPT Algorithm for Min-<i>k</i>-Cut Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
The constant inapproximability of the parameterized dominating set problem SIAM Journal on Computing	2019-05-07	Paper
The parameterized complexity of the k-biclique problem Journal of the ACM	2019-02-25	Paper
The hardness of embedding grids and walls (available as arXiv preprint)	2018-01-04	Paper
The parameterized complexity of k-biclique Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms	2017-10-05	Paper
The parameterized complexity of k-edge induced subgraphs Information and Computation	2016-12-22	Paper
Multi-multiway cut problem on graphs of bounded branch width Frontiers in Algorithmics and Algorithmic Aspects in Information and Management	2014-04-03	Paper
The Parameterized Complexity of k-Edge Induced Subgraphs Automata, Languages, and Programming	2013-08-12	Paper

Research outcomes over time

This page was built for person: Bingkai Lin