Sungjin Im
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
Research Subjects
Sungjin Im has a total of 49 co-authors. Here are the top co-authors by number of shared publications:
- Benjamin Moseley
Carnegie Mellon University, Pittsburgh, PA, USA
18 shared publications - Kirk Pruhs
University of Pittsburgh, Pittsburgh, PA, USA
6 shared publications - Qingyun Chen
Electrical Engineering and Computer Science University of California 5200 N. Lake Road 95344 Merced CA
6 shared publications - Kamesh Munagala
Duke University, Durham, USA
5 shared publications - Aditya Bhaskara
School of Computing University of Utah
3 shared publications - Chenyang Xu
East China Normal University
3 shared publications
Latest Publications
- Top Cited Papers
- 2 January 2026
- Published by Springer Nature
- p. 401-419
Strategic Facility Location via Predictions
- 2 January 2026
- Published by Springer Nature
- p. 401-419
Top Cited PapersStrategic Facility Location via Predictions
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-26
Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robust and practical information-theoretic cardinality estimation framework. In this framework, the estimator is the cardinality upper bound of a conjunctive query subject to ''degree-constraints'', which model a rich set of input data statistics. For general degree constraints, computing this bound is computationally hard. Researchers have naturally sought efficiently computable relaxed upper bounds that are as tight as possible. The polymatroid bound is the tightest among those relaxed upper bounds. While it is an open question whether the polymatroid bound can be computed in polynomial-time in general, it is known to be computable in polynomial-time for some classes of degree constraints. Our focus is on a common class of degree constraints called simple degree constraints. Researchers had not previously determined how to compute the polymatroid bound in polynomial time for this class of constraints. Our first main result is a polynomial time algorithm to compute the polymatroid bound given simple degree constraints. Our second main result is a polynomial-time algorithm to compute a ''proof sequence'' establishing this bound. This proof sequence can then be incorporated in the PANDA-framework to give a faster algorithm to evaluate a conjunctive query. In addition, we show computational limitations to extending our results to broader classes of degree constraints. Finally, our technique leads naturally to a new relaxed upper bound called the flow bound, which is computationally tractable.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-26
Open AccessEfficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
Cardinality estimation and conjunctive query evaluation are two of the most fundamental problems in database query processing. Recent work proposed, studied, and implemented a robust and practical information-theoretic cardinality estimation framework. In this framework, the estimator is the cardinality upper bound of a conjunctive query subject to ''degree-constraints'', which model a rich set of input data statistics. For general degree constraints, computing this bound is computationally hard. Researchers have naturally sought efficiently computable relaxed upper bounds that are as tight as possible. The polymatroid bound is the tightest among those relaxed upper bounds. While it is an open question whether the polymatroid bound can be computed in polynomial-time in general, it is known to be computable in polynomial-time for some classes of degree constraints. Our focus is on a common class of degree constraints called simple degree constraints. Researchers had not previously determined how to compute the polymatroid bound in polynomial time for this class of constraints. Our first main result is a polynomial time algorithm to compute the polymatroid bound given simple degree constraints. Our second main result is a polynomial-time algorithm to compute a ''proof sequence'' establishing this bound. This proof sequence can then be incorporated in the PANDA-framework to give a faster algorithm to evaluate a conjunctive query. In addition, we show computational limitations to extending our results to broader classes of degree constraints. Finally, our technique leads naturally to a new relaxed upper bound called the flow bound, which is computationally tractable.
- Open Access
Binary Search with Distributional Predictions
Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a distribution. We initiate the study of algorithms with distributional predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log η)$, where $H(p)$ is the entropy of the true distribution $p$ and $η$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first distributionally-robust algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.Open AccessBinary Search with Distributional Predictions
Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a distribution. We initiate the study of algorithms with distributional predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log η)$, where $H(p)$ is the entropy of the true distribution $p$ and $η$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first distributionally-robust algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm. - Open Access
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-19
Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
Datalog o is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike Datalog, the natural iterative evaluation of some Datalogo programs over some semirings may not converge. It is known that the commutative semirings for which the iterative evaluation of Datalogo programs is guaranteed to converge are exactly those semirings that are stable. Previously, the best known upper bound on the number of iterations until convergence over p-stable semirings is ∑i=1 ^n (p+2) i = Θ(p n ) steps, where n is (essentially) the output size. We establish that, in fact, the natural iterative evaluation of a Datalogo program over a p-stable semiring converges within a polynomial number of iterations. In particular our upper bound is O(σ p n 2 ( n 2 lg Λ + lg σ)) where σ is the number of elements in the semiring present in either the input databases or the Datalogo program, and λ is the maximum number of terms in any product in the Datalogo program.
- 4 November 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (5) , 1-19
Open AccessPolynomial Time Convergence of the Iterative Evaluation of Datalogo Programs
Datalog o is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike Datalog, the natural iterative evaluation of some Datalogo programs over some semirings may not converge. It is known that the commutative semirings for which the iterative evaluation of Datalogo programs is guaranteed to converge are exactly those semirings that are stable. Previously, the best known upper bound on the number of iterations until convergence over p-stable semirings is ∑i=1 ^n (p+2) i = Θ(p n ) steps, where n is (essentially) the output size. We establish that, in fact, the natural iterative evaluation of a Datalogo program over a p-stable semiring converges within a polynomial number of iterations. In particular our upper bound is O(σ p n 2 ( n 2 lg Λ + lg σ)) where σ is the number of elements in the semiring present in either the input databases or the Datalogo program, and λ is the maximum number of terms in any product in the Datalogo program.
- Open Access
Strategic Facility Location via Predictions
The facility location with strategic agents is a canonical problem in the literature on mechanism design without money. Recently, Agrawal et. al. considered this problem in the context of machine learning augmented algorithms, where the mechanism designer is also given a prediction of the optimal facility location. An ideal mechanism in this framework produces an outcome that is close to the social optimum when the prediction is accurate (consistency) and gracefully degrades as the prediction deviates from the truth, while retaining some of the worst-case approximation guarantees (robustness). The previous work only addressed this problem in the two-dimensional Euclidean space providing optimal trade-offs between robustness and consistency guarantees for deterministic mechanisms. We consider the problem for \emph{general} metric spaces. Our only assumption is that the metric is continuous, meaning that any pair of points must be connected by a continuous shortest path. We introduce a novel mechanism that in addition to agents' reported locations takes a predicted optimal facility location $\hat{o}$. We call this mechanism $\texttt{Harmonic}$, as it selects one of the reported locations $\tilde{\ell}_i$ with probability inversely proportional to $d(\hat{o},\tilde{\ell}_i)+ Δ$ for a constant parameter $Δ$. While \harm \ mechanism is not truthful, we can \emph{characterize the set of undominated strategies} for each agent $i$ as solely consisting of the points on a shortest path from their true location $\ell_i$ to the predicted location $\hat{o}$. We further derive \emph{consistency and robustness guarantees on the Price of Anarchy (PoA)} for the game induced by the mechanism.Open AccessStrategic Facility Location via Predictions
The facility location with strategic agents is a canonical problem in the literature on mechanism design without money. Recently, Agrawal et. al. considered this problem in the context of machine learning augmented algorithms, where the mechanism designer is also given a prediction of the optimal facility location. An ideal mechanism in this framework produces an outcome that is close to the social optimum when the prediction is accurate (consistency) and gracefully degrades as the prediction deviates from the truth, while retaining some of the worst-case approximation guarantees (robustness). The previous work only addressed this problem in the two-dimensional Euclidean space providing optimal trade-offs between robustness and consistency guarantees for deterministic mechanisms. We consider the problem for \emph{general} metric spaces. Our only assumption is that the metric is continuous, meaning that any pair of points must be connected by a continuous shortest path. We introduce a novel mechanism that in addition to agents' reported locations takes a predicted optimal facility location $\hat{o}$. We call this mechanism $\texttt{Harmonic}$, as it selects one of the reported locations $\tilde{\ell}_i$ with probability inversely proportional to $d(\hat{o},\tilde{\ell}_i)+ Δ$ for a constant parameter $Δ$. While \harm \ mechanism is not truthful, we can \emph{characterize the set of undominated strategies} for each agent $i$ as solely consisting of the points on a shortest path from their true location $\ell_i$ to the predicted location $\hat{o}$. We further derive \emph{consistency and robustness guarantees on the Price of Anarchy (PoA)} for the game induced by the mechanism. - Open Access
Online Scheduling via Gradient Descent for Weighted Flow Time Minimization
In this paper, we explore how a natural generalization of Shortest Remaining Processing Time (SRPT) can be a powerful \emph{meta-algorithm} for online scheduling. The meta-algorithm processes jobs to maximally reduce the objective of the corresponding offline scheduling problem of the remaining jobs: minimizing the total weighted completion time of them (the residual optimum). We show that it achieves scalability for minimizing total weighted flow time when the residual optimum exhibits \emph{supermodularity}. Scalability here means it is $O(1)$-competitive with an arbitrarily small speed augmentation advantage over the adversary, representing the best possible outcome achievable for various scheduling problems. Thanks to this finding, our approach does not require the residual optimum to have a closed mathematical form. Consequently, we can obtain the schedule by solving a linear program, which makes our approach readily applicable to a rich body of applications. Furthermore, by establishing a novel connection to \emph{substitute valuations in Walrasian markets}, we show how to achieve supermodularity, thereby obtaining scalable algorithms for various scheduling problems, such as matroid scheduling, generalized network flow, and generalized arbitrary speed-up curves, etc., and this is the \emph{first} non-trivial or scalable algorithm for many of them.
Open AccessOnline Scheduling via Gradient Descent for Weighted Flow Time Minimization
In this paper, we explore how a natural generalization of Shortest Remaining Processing Time (SRPT) can be a powerful \emph{meta-algorithm} for online scheduling. The meta-algorithm processes jobs to maximally reduce the objective of the corresponding offline scheduling problem of the remaining jobs: minimizing the total weighted completion time of them (the residual optimum). We show that it achieves scalability for minimizing total weighted flow time when the residual optimum exhibits \emph{supermodularity}. Scalability here means it is $O(1)$-competitive with an arbitrarily small speed augmentation advantage over the adversary, representing the best possible outcome achievable for various scheduling problems. Thanks to this finding, our approach does not require the residual optimum to have a closed mathematical form. Consequently, we can obtain the schedule by solving a linear program, which makes our approach readily applicable to a rich body of applications. Furthermore, by establishing a novel connection to \emph{substitute valuations in Walrasian markets}, we show how to achieve supermodularity, thereby obtaining scalable algorithms for various scheduling problems, such as matroid scheduling, generalized network flow, and generalized arbitrary speed-up curves, etc., and this is the \emph{first} non-trivial or scalable algorithm for many of them.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 491-497
Online Load and Graph Balancing for Random Order Inputs
Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In the adversarial setting, where an adversary chooses not only the collection of job sizes but also their arrival order, the problem is well-understood and the optimal competitive ratio is known to be Θ(log m) where m is the number of machines. In the more realistic random arrival order model, the understanding is limited. Previously, the best lower bound on the competitive ratio was only Ω(log log m). We significantly improve this bound by showing an Ω( √log m) lower bound, even for the restricted case where each job has a unit size on two machines and infinite size on the others. On the positive side, we propose an O(log m/log log m)-competitive algorithm, demonstrating that better performance is possible in the random arrival model.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 491-497
Open AccessOnline Load and Graph Balancing for Random Order Inputs
Online load balancing for heterogeneous machines aims to minimize the makespan (maximum machine workload) by scheduling arriving jobs with varying sizes on different machines. In the adversarial setting, where an adversary chooses not only the collection of job sizes but also their arrival order, the problem is well-understood and the optimal competitive ratio is known to be Θ(log m) where m is the number of machines. In the more realistic random arrival order model, the understanding is limited. Previously, the best lower bound on the competitive ratio was only Ω(log log m). We significantly improve this bound by showing an Ω( √log m) lower bound, even for the restricted case where each job has a unit size on two machines and infinite size on the others. On the positive side, we propose an O(log m/log log m)-competitive algorithm, demonstrating that better performance is possible in the random arrival model.
- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 57-65
Data Exchange Markets via Utility Balancing
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 57-65
Open AccessData Exchange Markets via Utility Balancing
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.
- Open Access
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20649-20656
Sampling for Beyond-Worst-Case Online Ranking
The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20649-20656
Open AccessSampling for Beyond-Worst-Case Online Ranking
The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.
- Open Access
Data Exchange Markets via Utility Balancing
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.
Open AccessData Exchange Markets via Utility Balancing
This paper explores the design of a balanced data-sharing marketplace for entities with heterogeneous datasets and machine learning models that they seek to refine using data from other agents. The goal of the marketplace is to encourage participation for data sharing in the presence of such heterogeneity. Our market design approach for data sharing focuses on interim utility balance, where participants contribute and receive equitable utility from refinement of their models. We present such a market model for which we study computational complexity, solution existence, and approximation algorithms for welfare maximization and core stability. We finally support our theoretical insights with simulations on a mean estimation task inspired by road traffic delay estimation.