Pattara Sukprasert

Dr. Pattara Sukprasert

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2020
Verified
Book Chapter
Closed access
PCParinya Chalermsook
Parinya Chalermsook
SKSamir Khuller
Samir Khuller
PSPattara Sukprasert
Pattara Sukprasert
SUSumedha Uniyal
Sumedha Uniyal
In this paper, we study a primal and dual relationship about triangles: For any graph G, let v(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that v(G) ≤ τ(G) ≤ 3v(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2v(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kv(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.

4 March 2025 in Algorithms
Verified
Journal Article
Open access
PDF file
NSNoah Schulhof
Noah Schulhof
PSPattara Sukprasert
Pattara Sukprasert
EREytan Ruppin
Eytan Ruppin
SKSamir Khuller
Samir Khuller
ASAlejandro A. Schäffer
Alejandro A. Schäffer
Integer linear programs (ILPs) and mixed integer programs (MIPs) often have multiple distinct optimal solutions, yet the widely used Gurobi optimization solver returns certain solutions at disproportionately high frequencies. This behavior is disadvantageous, as, in fields such as biomedicine, the identification and analysis of distinct optima yields valuable domain-specific insights that inform future research directions. In the present work, we introduce MORSE (Multiple Optima via Random Sampling and careful choice of the parameter Epsilon), a randomized, parallelizable algorithm to efficiently generate multiple optima for ILPs. MORSE maps multiplicative perturbations to the coefficients in an instance’s objective function, generating a modified instance that retains an optimum of the original problem. We formalize and prove the above claim in some practical conditions. Furthermore, we prove that for 0/1 selection problems, MORSE finds each distinct optimum with equal probability. We evaluate MORSE using two measures; the number of distinct optima found in r independent runs, and the diversity of the list (with repetitions) of solutions by average pairwise Hamming distance and Shannon entropy. Using these metrics, we provide empirical results demonstrating that MORSE outperforms the Gurobi method and unweighted variations of the MORSE method on a set of 20 Mixed Integer Programming Library (MIPLIB) instances and on a combinatorial optimization problem in cancer genomics.

1 July 2018
Verified
Conference Paper
Closed access
JFJittat Fakcharoephol
Jittat Fakcharoephol
PSPattara Sukprasert
Pattara Sukprasert
We present an n O(1/ε) PTAS for minimum dominating set problem in unit disk graphs. Our approach gives an asymptotic improvement over the best known [Nieberg and Hurink WAOA2005], which runs in n O(1/ε log 1/ε) , under a more strict (but typical) assumption that the underlying geometric structure is known, i.e., the locations of all unit disks are specified. Our key ingredient is an improved dynamic programming algorithm that depends exponentially on a more essential 1-dimensional “width” of the problem.

29 January 2020 in bioRxiv
Verified
Preprint
Open access
PDF file
SASaba Ahmadi
Saba Ahmadi
PSPattara Sukprasert
Pattara Sukprasert
RVRahulsimham Vegesna
Rahulsimham Vegesna
SSSanju Sinha
Sanju Sinha
FSFiorella Schischlik
Fiorella Schischlik
EREytan Ruppin
Eytan Ruppin
The availability of single-cell transcriptomics data opens new opportunities for rational design of combination cancer treatments. Mining such data, we employed combinatorial optimization techniques to explore the landscape of optimal combination therapies in solid tumors including brain, head and neck, melanoma, lung, breast and colon cancers. We assume that each individual therapy can target any one of 1269 genes encoding cell surface receptors, which may be targets of CAR-T, conjugated antibodies or coated nanoparticle therapies. As a baseline case, we studied the killing of at least 80% of the tumor cells while sparing more than 90% of the non-tumor cells in each patient, as a putative regimen. We find that in most cancer types, personalized combinations composed of at most four targets are then sufficient. However, the number of distinct targets that one would need to assemble to treat all patients in a cohort accordingly would be around 10 in most cases. Further requiring that the target genes be also lowly expressed in healthy tissues uncovers qualitatively similar trends. However, as one asks for more stringent and selective killing beyond the baseline regimen we focused on, we find that the number of targets needed rises rapidly. Emerging individual promising receptor targets includePTPRZ1, which is frequently found in the optimal combinations for brain and head and neck cancers, andEGFR, a recurring target in multiple tumor types. In sum, this systematic single-cell based characterization of the landscape of combinatorial receptor-mediated cancer treatments establishes first of their kind estimates on the number of targets needed, identifying promising ones for future development.

28 September 2023 in arXiv
Verified
Preprint
Open access
PDF file
AAAnders Aamand
Anders Aamand
JCJustin Y. Chen
Justin Y. Chen
ALAllen Liu
Allen Liu
SSSandeep Silwal
Sandeep Silwal
PSPattara Sukprasert
Pattara Sukprasert
FZFred Zhang
Fred Zhang
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is $α$-IP stable if the average distance of every data point to its own cluster is at most $α$ times the average distance to any other cluster. Unfortunately, determining if a dataset admits a $1$-IP stable clustering is NP-Hard. Moreover, before this work, it was unknown if an $o(n)$-IP stable clustering always \emph{exists}, as the prior state of the art only guaranteed an $O(n)$-IP stable clustering. We close this gap in understanding and show that an $O(1)$-IP stable clustering always exists for general metrics, and we give an efficient algorithm which outputs such a clustering. We also introduce generalizations of IP stability beyond average distance and give efficient, near-optimal algorithms in the cases where we consider the maximum and minimum distances within and between clusters.

3 February 2021 in arXiv
Verified
Preprint
Open access
PDF file
PCParinya Chalermsook
Parinya Chalermsook
SKSamir Khuller
Samir Khuller
PSPattara Sukprasert
Pattara Sukprasert
SUSumedha Uniyal
Sumedha Uniyal
In this paper, we study a primal and dual relationship about triangles: For any graph $G$, let $\nu(G)$ be the maximum number of edge-disjoint triangles in $G$, and $\tau(G)$ be the minimum subset $F$ of edges such that $G \setminus F$ is triangle-free. It is easy to see that $\nu(G) \leq \tau(G) \leq 3 \nu(G)$, and in fact, this rather obvious inequality holds for a much more general primal-dual relation between $k$-hyper matching and covering in hypergraphs. Tuza conjectured in $1981$ that $\tau(G) \leq 2 \nu(G)$, and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every $k \geq 2$, there exist a (multi)-set $F \subseteq E(G): |F| \leq 2k \nu(G)$ such that each triangle in $G$ overlaps at least $k$ elements in $F$. Our result can be seen as a strengthened statement of Krivelevich's result on the fractional version of Tuza's conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in $F$ based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza's conjecture in particular.