Samir Khuller

Prof. Dr. Samir Khuller

orcid

Research Focus & Metrics

Academic Career Length

30Years (1997-Present)

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

Representative Publications

View All Publications
17 January 2010
Verified
Conference Paper
Open access
SKSamir Khuller
Samir Khuller
JLJian Li
Jian Li
BSBarna Saha
Barna Saha

15 July 2020 in Algorithmica
Verified
Journal Article
Closed access
PDF file
SASaba Ahmadi
Saba Ahmadi
SKSamir Khuller
Samir Khuller
MPManish Purohit
Manish Purohit
SYSheng Yang
Sheng Yang

1 January 2006
Verified
Book Chapter
Open access
PDF file
JBJens Bleiholder
Jens Bleiholder
SKSamir Khuller
Samir Khuller
FNFelix Naumann
Felix Naumann
LRLouiqa Raschid
Louiqa Raschid
YWYao Wu
Yao Wu
Navigational queries on Web-accessible life science sources pose unique query optimization challenges. The objects in these sources are interconnected to objects in other sources, forming a large and complex graph, and there is an overlap of objects in the sources. Answering a query requires the traversal of multiple alternate paths through these sources. Each path can be associated with the benefit or the cardinality of the target object set (TOS) of objects reached in the result. There is also an evaluation cost of reaching the TOS. We present dual problems in selecting the best set of paths. The first problem is to select a set of paths that satisfy a constraint on the evaluation cost while maximizing the benefit (number of distinct objects in the TOS). The dual problem is to select a set of paths that satisfies a threshold of the TOS benefit with minimal evaluation cost. The two problems can be mapped to the budgeted maximum coverage problem and the maximal set cover with a threshold. To solve these problems, we explore several solutions including greedy heuristics, a randomized search, and a traditional IP/LP formulation with bounds. We perform experiments on a real-world graph of life sciences objects from NCBI and report on the computational overhead of our solutions and their performance compared to the optimal solution.

2 June 2022 in Discrete Optimization
Verified
Journal Article
Closed access
SGSapna Grover
Sapna Grover
NGNeelima Gupta
Neelima Gupta
SKSamir Khuller
Samir Khuller

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.

12 February 2020 in arXiv
Verified
Preprint
Open access
PDF file
SASaba Ahmadi
Saba Ahmadi
FAFaez Ahmed
Faez Ahmed
JDJohn P. Dickerson
John P. Dickerson
MFMark Fuge
Mark Fuge
SKSamir Khuller
Samir Khuller
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.