Samir Khuller
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Samir Khuller has a total of 31 co-authors. Here are the top co-authors by number of shared publications:
- Pattara Sukprasert
Databricks Inc., San Francisco, CA 94105, USA
4 shared publications - Alejandro Schaffer
Cancer Data Science Laboratory, Center for Cancer Research, National Cancer Institute, National Institutes of Health, Bethesda, USA
3 shared publications - Eytan Ruppin
Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD, USA
3 shared publications - Noah Schulhof
Cancer Data Science Laboratory, National Cancer Institute, National Institutes of Health, Bethesda, MD 20892, USA
2 shared publications - Saba Ahmadi
Department of Computer Science University of Maryland
2 shared publications Barna Saha
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 37-49
Online Span Minimization for Flexible Uniform Jobs
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 37-49
Open AccessOnline Span Minimization for Flexible Uniform Jobs
- Open Access
- 4 March 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (3) , 140
Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function
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.
- 4 March 2025
- Published by MDPI AG in Algorithms
- Vol. 18 (3) , 140
Open AccessFinding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of Its Objective Function
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.
- Open Access
- 21 January 2025
- Published by MDPI AG in Preprints.org
Finding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of its Objective Function
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.- 21 January 2025
- Published by MDPI AG in Preprints.org
Open AccessFinding Multiple Optimal Solutions to an Integer Linear Program by Random Perturbations of its Objective Function
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. - Open Access
- 7 November 2022
- Published by Springer Nature in Journal of Scheduling
- Vol. 26 (5) , 1
Special Issue on papers from the 2019 Workshop on Models and Algorithms for Planning and Scheduling Problems
- 7 November 2022
- Published by Springer Nature in Journal of Scheduling
- Vol. 26 (5) , 1
Open AccessSpecial Issue on papers from the 2019 Workshop on Models and Algorithms for Planning and Scheduling Problems
- Open Access
Correlated Stochastic Knapsack with a Submodular Objective
We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time $(1 - 1/\sqrt{e})/2 \simeq 0.1967$ approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the $(1 - 1/\sqrt[4]{e})/2 \simeq 0.1106$ approximation by Fukunaga et al. [AAAI 2019].Open AccessCorrelated Stochastic Knapsack with a Submodular Objective
We study the correlated stochastic knapsack problem of a submodular target function, with optional additional constraints. We utilize the multilinear extension of submodular function, and bundle it with an adaptation of the relaxed linear constraints from Ma [Mathematics of Operations Research, Volume 43(3), 2018] on correlated stochastic knapsack problem. The relaxation is then solved by the stochastic continuous greedy algorithm, and rounded by a novel method to fit the contention resolution scheme (Feldman et al. [FOCS 2011]). We obtain a pseudo-polynomial time $(1 - 1/\sqrt{e})/2 \simeq 0.1967$ approximation algorithm with or without those additional constraints, eliminating the need of a key assumption and improving on the $(1 - 1/\sqrt[4]{e})/2 \simeq 0.1106$ approximation by Fukunaga et al. [AAAI 2019]. - 2 June 2022
- Published by Elsevier in Discrete Optimization
- Vol. 45
LP-based approximation for uniform capacitated facility location problem
- 2 June 2022
- Published by Elsevier in Discrete Optimization
- Vol. 45
LP-based approximation for uniform capacitated facility location problem
- Open Access
Multi-transversals for Triangles and the Tuza's Conjecture
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.Open AccessMulti-transversals for Triangles and the Tuza's Conjecture
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. - 15 July 2020
- Published by Springer Nature in Algorithmica
- Vol. 82 (12) , 3604-3629
On Scheduling Coflows
- 15 July 2020
- Published by Springer Nature in Algorithmica
- Vol. 82 (12) , 3604-3629
On Scheduling Coflows
- Open Access
An Algorithm for Multi-Attribute Diverse Matching
Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application.
Open AccessAn Algorithm for Multi-Attribute Diverse Matching
Bipartite b-matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application.
- Open Access
- 29 January 2020
- Published by Cold Spring Harbor Laboratory in bioRxiv
The Landscape of Receptor-Mediated Precision Cancer Combination Therapy: A Single-Cell Perspective
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.
- 29 January 2020
- Published by Cold Spring Harbor Laboratory in bioRxiv
Open AccessThe Landscape of Receptor-Mediated Precision Cancer Combination Therapy: A Single-Cell Perspective
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.