Search Results

Documents authored by Tan, Junqi


Document
Exact Algorithms for Optimal Discretization

Authors: László Kozma and Junqi Tan

Published in: LIPIcs, Volume 398, 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)


Abstract
The optimal discretization problem asks, given two disjoint sets of points R and B in the plane, for a minimal family of horizontal and vertical lines that separate the two sets, so that no cell delimited by the lines contains points from both sets. The problem arises as a pre-processing in supervised machine learning, and has received significant attention in parameterized algorithmics. Answering the question raised by Bonnet, Giannopoulos, and Lampis [IPEC 2017] and Froese [PhD thesis, 2018], it was shown by Kratsch, Masařík, Muzi, Pilipczuk, and Sorge [SODA 2021] that optimal discretization admits a fixed-parameter algorithm with running time 2^𝒪(k²log{k}) ⋅ n^𝒪(1), where k is the solution size and n = |R| + |B|. In this paper we give an algorithm for optimal discretization that runs in time 𝒪(1.9602ⁿ). We also study the related point separation problem that asks to separate all input points by axis-parallel lines. For this problem we obtain an algorithm with runtime 𝒪(1.8906ⁿ). Our guarantees follow from structural observations about bichromatic and monochromatic point sets, and hold even if points are allowed to share coordinates. To our knowledge, these are the first improvements over the trivial 2ⁿ bound for both problems.

Cite as

László Kozma and Junqi Tan. Exact Algorithms for Optimal Discretization. In 21st International Symposium on Parameterized and Exact Computation (IPEC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 398, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.IPEC.2026.8,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Exact Algorithms for Optimal Discretization}},
  booktitle =	{21st International Symposium on Parameterized and Exact Computation (IPEC 2026)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-456-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{398},
  editor =	{Korhonen, Tuukka and Lampis, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2026.8},
  URN =		{urn:nbn:de:0030-drops-281815},
  doi =		{10.4230/LIPIcs.IPEC.2026.8},
  annote =	{Keywords: discretization, point set, separation, exponential time}
}
Document
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

Authors: László Kozma and Junqi Tan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)


Abstract
For many hard computational problems, simple algorithms that run in time 2ⁿ ⋅ n^O(1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this paper we obtain algorithms with running time O(1.9999977ⁿ) on input graphs with n vertices, for the following well-studied problems: - d-Cut: find a proper cut in which no vertex has more than d neighbors on the other side of the cut; - Internal Partition: find a proper cut in which every vertex has at least as many neighbors on its side of the cut as on the other side; and - (α,β)-Domination: given intervals α,β ⊆ [0,n], find a subset S of the vertices, so that for every vertex v ∈ S the number of neighbors of v in S is from α and for every vertex v ∉ S, the number of neighbors of v in S is from β. Our algorithms are exceedingly simple, combining the split and list technique (Horowitz and Sahni, 1974; Williams, 2005) with a tool from computational geometry: orthogonal range searching in the moderate dimensional regime (Chan, 2017). Our technique is applicable to the decision, optimization and counting versions of these problems and easily extends to various generalizations with more fine-grained, vertex-specific constraints, as well as to directed, balanced, and other variants. Algorithms with running times of the form cⁿ, for c < 2, were known for the first problem only for constant d, and for the third problem for certain special cases of α and β; for the second problem we are not aware of such results.

Cite as

László Kozma and Junqi Tan. Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 110:1-110:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2025.110,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Faster Exponential Algorithms for Cut Problems via Geometric Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{110:1--110:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.110},
  URN =		{urn:nbn:de:0030-drops-245796},
  doi =		{10.4230/LIPIcs.ESA.2025.110},
  annote =	{Keywords: graph algorithms, cuts, exponential time, data structures}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail