Arrow Research search

Author name cluster

Sungjin Im

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

33 papers
2 author rows

Possible papers

33

NeurIPS Conference 2025 Conference Paper

A Beyond-Worst-Case Analysis of Greedy k-means++

  • Qingyun Chen
  • Sungjin Im
  • Ben Moseley
  • Ryan Milstrey
  • Chenyang Xu
  • Ruilong Zhang

$k$-means++ and the related greedy $k$-means++ algorithm are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy $k$-means++ is a generalization of $k$-means++ where, in each iteration, a new seed is greedily chosen among multiple $\ell \geq 2$ points sampled, as opposed to a single seed being sampled in $k$-means++. While empirical studies consistently show the superior performance of greedy $k$-means++, making it a preferred method in practice, a discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy $k$-means++ exhibits worse performance than $k$-means++ in worst-case scenarios. This paper presents an analysis demonstrating the outperformance of the greedy algorithm compared to $k$-means++ for a natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when $\ell = \Theta(\log k)$, a common parameter setting in practical applications.

PDF Details

NeurIPS Conference 2024 Conference Paper

Binary Search with Distributional Predictions

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Aidin Niaparast
  • Sergei Vassilvitskii

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 \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ 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.

PDF Details DOI

SODA Conference 2024 Conference Paper

Controlling Tail Risk in Online Ski-Rental

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is e / e -1-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and the change of the competitive ratio exceeding n is Θ(1/ n )! We ask what happens to the optimal solution if we insist that the tail risk, i. e. , the chance of the competitive ratio exceeding a specific value, is bounded by some constant δ. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and arbitrarily large (for sufficiently small tail risk δ and large purchase cost n ). * A full version of the paper can be accessed at https: //arxiv. org/abs/2308. 05067

Details

AAAI Conference 2024 Conference Paper

Sampling for Beyond-Worst-Case Online Ranking

  • Qingyun Chen
  • Sungjin Im
  • Benjamin Moseley
  • Chenyang Xu
  • Ruilong Zhang

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.

PDF Details DOI

SODA Conference 2023 Conference Paper

Improved Approximations for Unrelated Machine Scheduling

  • Sungjin Im
  • Shi Li 0001

We revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted completion time we give a 1. 45-approximation, which improves upon the previous 1. 488-approximation [Im and Shadloo SODA 2020]. The key technical ingredient in this improvement lies in a new rounding scheme that gives strong negative correlation with less restrictions. For minimizing L k -norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a -approximation for the L 2 -norm which improves upon the former -approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].

Details

AAAI Conference 2023 Conference Paper

Min-Max Submodular Ranking for Multiple Agents

  • Qingyun Chen
  • Sungjin Im
  • Benjamin Moseley
  • Chenyang Xu
  • Ruilong Zhang

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

Algorithms with Prediction Portfolios

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.

PDF Details

ICML Conference 2022 Conference Paper

Parsimonious Learning-Augmented Caching

  • Sungjin Im
  • Ravi Kumar 0001
  • Aditya Petety
  • Manish Purohit

Learning-augmented algorithms—in which, traditional algorithms are augmented with machine-learned predictions—have emerged as a framework to go beyond worst-case analysis. The overarching goal is to design algorithms that perform near-optimally when the predictions are accurate yet retain certain worst-case guarantees irrespective of the accuracy of the predictions. This framework has been successfully applied to online problems such as caching where the predictions can be used to alleviate uncertainties. In this paper we introduce and study the setting in which the learning-augmented algorithm can utilize the predictions parsimoniously. We consider the caching problem—which has been extensively studied in the learning-augmented setting—and show that one can achieve quantitatively similar results but only using a sublinear number of predictions.

Details

MFCS Conference 2021 Conference Paper

An Approximation Algorithm for the Matrix Tree Multiplication Problem

  • Mahmoud Abo Khamis
  • Ryan R. Curtin
  • Sungjin Im
  • Benjamin Moseley
  • Hung Q. Ngo 0001
  • Kirk Pruhs
  • Alireza Samadian

We consider the Matrix Tree Multiplication problem. This problem is a generalization of the classic Matrix Chain Multiplication problem covered in the dynamic programming chapter of many introductory algorithms textbooks. An instance of the Matrix Tree Multiplication problem consists of a rooted tree with a matrix associated with each edge. The output is, for each leaf in the tree, the product of the matrices on the chain/path from the root to that leaf. Matrix multiplications that are shared between various chains need only be computed once, potentially being shared between different root to leaf chains. Algorithms are evaluated by the number of scalar multiplications performed. Our main result is a linear time algorithm for which the number of scalar multiplications performed is at most 15 times the optimal number of scalar multiplications.

Details

NeurIPS Conference 2021 Conference Paper

Faster Matchings via Learned Duals

  • Michael Dinitz
  • Sungjin Im
  • Thomas Lavastida
  • Benjamin Moseley
  • Sergei Vassilvitskii

A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of ``warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.

PDF Details

NeurIPS Conference 2021 Conference Paper

Online Knapsack with Frequency Predictions

  • Sungjin Im
  • Ravi Kumar
  • Mahshid Montazer Qaem
  • Manish Purohit

There has been recent interest in using machine-learned predictions to improve the worst-case guarantees of online algorithms. In this paper we continue this line of work by studying the online knapsack problem, but with very weak predictions: in the form of knowing an upper and lower bound for the number of items of each value. We systematically derive online algorithms that attain the best possible competitive ratio for any fixed prediction; we also extend the results to more general settings such as generalized one-way trading and two-stage online knapsack. Our work shows that even seemingly weak predictions can be utilized effectively to provably improve the performance of online algorithms.

PDF Details

TCS Journal 2018 Journal Article

Energy efficient scheduling of parallelizable jobs

  • Kyle Fox
  • Sungjin Im
  • Benjamin Moseley

This paper considers scheduling parallelizable jobs in the non-clairvoyant speed scaling setting to minimize the objective of weighted flow time plus energy. Previously, strong lower bounds were shown on this model in the unweighted setting even when the algorithm is given a constant amount of resource augmentation over the optimal solution. However, these lower bounds were given only for certain families of algorithms that do not recognize the parallelizability of alive jobs. In this work, we circumvent previous lower bounds shown and give a scalable algorithm under the natural assumption that the algorithm can know the current parallelizability of a job. When a general power function is considered, this is also the first algorithm that has a constant competitive ratio for the problem using any amount of resource augmentation.

Details DOI

STOC Conference 2018 Conference Paper

Online load balancing on related machines

  • Sungjin Im
  • Nathaniel Kell
  • Debmalya Panigrahi
  • Maryam Shadloo

In this paper, we consider the problem of assigning jobs online to machines with non-uniform speeds (also called related machines ) so to optimize a given norm of the machine loads. A long line of work, starting with the seminal work of Graham in the 1960s, has led to tight competitive ratios for all ℓ q norms for two scenarios: the special case of identical machines (uniform machine speeds) and the more general setting of unrelated machines (jobs have arbitrary processing times on machines). For non-uniform machine speeds, however, the only known result was a constant competitive competitive ratio for the makespan (ℓ ∞ ) norm, via the so-called slowest-fit algorithm (Aspnes, Azar, Fiat, Plotkin, and Waarts, JACM ’97). Our first result in this paper is to obtain the first constant-competitive algorithm for scheduling on related machines for any arbitrary ℓ q norm . Recent literature has further expanded the scope of this problem to vector scheduling , to capture multi-dimensional resource requirements in applications such as data centers. As in the scalar case, tight bounds are known for vector scheduling on identical and unrelated machines. Our second set of results is to give tight competitive ratios for vector scheduling on related machines for the makespan and all ℓ q norms . No previous bounds were known, even for the makespan norm, for related machines. We employ a convex relaxation of the ℓ q -norm objective and use a continuous greedy algorithm to solve this convex program online. To round the fractional solution, we then use a novel restructuring of the instance that we call machine smoothing . This is a generic tool that reduces a problem on related machines to a set of problem instances on identical machines, and we hope it will be useful in other settings with non-uniform machine speeds as well.

Details

STOC Conference 2017 Conference Paper

Efficient massively parallel methods for dynamic programming

  • Sungjin Im
  • Benjamin Moseley
  • Xiaorui Sun

Modern science and engineering is driven by massively large data sets and its advance heavily relies on massively parallel computing platforms such as Spark, MapReduce, and Hadoop. Theoretical models have been proposed to understand the power and limitations of such platforms. Recent study of developed theoretical models has led to the discovery of new algorithms that are fast and efficient in both theory and practice, thereby beginning to unlock their underlying power. Given recent promising results, the area has turned its focus on discovering widely applicable algorithmic techniques for solving problems efficiently.

Details

SODA Conference 2017 Conference Paper

Fair Scheduling via Iterative Quasi-Uniform Sampling

  • Sungjin Im
  • Benjamin Moseley

In the paper we consider minimizing the ℓ k -norms of flow time on a single machine offline using a preemptive scheduler for k ≥ 1. We show the first O ( 1)- approximation for the problem, improving upon the previous best O (log log P)-approximation by Bansal and Pruhs (FOCS 09 and SICOMP 14) where P is the ratio of the maximum job size to the minimum. Our main technical ingredient is a novel combination of quasi-uniform sampling and iterative rounding, which is of interest in its own right.

Details

FOCS Conference 2016 Conference Paper

Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions

  • Sungjin Im
  • Shi Li 0001

In this paper we consider the classic scheduling problem of minimizing total weighted completion time on unrelated machines when jobs have release times, i. e, R|r ij | Σ j w j C j using the three-field notation. For this problem, a 2-approximation is known based on a novel convex programming (J. ACM 2001 by Skutella). It has been a long standing open problem if one can improve upon this 2-approximation (Open Problem 8 in J. of Sched. 1999 by Schuurman and Woeginger). We answer this question in the affirmative by giving a 1. 8786-approximation. We achieve this via a surprisingly simple linear programming, but a novel rounding algorithm and analysis. A key ingredient of our algorithm is the use of random offsets sampled from non-uniform distributions. We also consider the preemptive version of the problem, i. e, R|r ij, pmtn|Σ j w j C j. We again use the idea of sampling offsets from non-uniform distributions to give the first better than 2-approximation for this problem. This improvement also requires use of a configuration LP with variables for each job's complete schedules along with more careful analysis. For both non-preemptive and preemptive versions, we break the approximation barrier of 2 for the first time.

Details

SODA Conference 2015 Conference Paper

A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]

  • Sungjin Im
  • Shi Li 0001
  • Benjamin Moseley
  • Eric Torng

In this paper, we consider a variety of scheduling problems where n jobs with release times are to be scheduled non-preemptively on a set of m identical machines. The problems considered are machine minimization, (weighted) throughput maximization and min-sum objectives such as (weighted) flow time and (weighted) tardiness. We develop a novel quasi-polynomial time dynamic programming framework that gives O (l)-speed O (l)-approximation algorithms for the offline versions of machine minimization and min-sum problems. For the weighted throughput problem, the framework gives a (1 + ε)-speed (1 – ε)-approximation algorithm. The generic DP is based on improving a naïve exponential time DP by developing a sketching scheme that compactly and accurately approximates parameters used in the DP states. We show that the loss of information due to the sketching scheme can be offset with limited resource augmentation. This framework is powerful and flexible, allowing us to apply it to this wide range of scheduling objectives and settings. We also provide new insight into the relative power of speed augmentation versus machine augmentation for non-preemptive scheduling problems; specifically, we give new evidence for the power and importance of extra speed for some non-preemptive scheduling problems. This novel DP framework leads to many new algorithms with improved results that solve many open problems, albeit with quasi-polynomial running times. We highlight our results as follows. For the problems with min-sum objectives, we give the first O (l)-speed O (l)-approximation algorithms for the multiple-machine setting. Even for the single machine case, we reduce both the resource augmentation required and the approximation ratios. In particular, our approximation ratios are either 1 or 1 + ε. Most of our algorithms use speed 1 + e or 2 + ε. We also resolve an open question (albeit with a quasi-polynomial time algorithm) of whether less than 2-speed could be used to achieve an O (1)-approximation for flow time. New techniques are needed to address this open question since it was proven that previous techniques are insufficient. We answer this open question by giving an algorithm that achieves a (1 + ε)-speed 1-approximation for flow time and (1 + ε)-speed (1 + ε)-approximation for weighted flow time. For the machine minimization problem, we give the first result using constant resource augmentation by showing a (1 + ε)-speed 2-approximation, and the first result only using speed augmentation and no additional machines by showing a (2 + ε)-speed 1-approximation. We complement our positive results for machine minimization by considering the discrete variant of the problem and show that no algorithm can use speed augmentation less than 2 log 1–ε and achieve approximation less than O (log log n ) for any constant ε > 0 unless NP admits quasi-polynomial time optimal algorithms. Thus, our results show a stark contrast between the two settings. In one, constant speed augmentation is sufficient whereas in the other, speed augmentation is essentially not effective.

Details

FOCS Conference 2015 Conference Paper

Competitive Flow Time Algorithms for Polyhedral Scheduling

  • Sungjin Im
  • Janardhan Kulkarni
  • Kamesh Munagala

Many scheduling problems can be viewed as allocating rates to jobs, subject to convex packing constraints on the rates. In this paper, we consider the problem of rate allocation when jobs of unknown size arrive online (non-clairvoyant setting), with the goal of minimizing weighted delay or flow time. Though this problem has strong lower bounds on competitive ratio in its full generality, we show positive results for natural and fairly broad sub-classes. More specifically, the subclasses we consider not only generalize several well-studied models such as scheduling with speedup curves and related machine scheduling, but also capture as special cases hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We establish several first positive results by making connections with two disparate disciplines: Economics and Queueing theory. First, we view the instantaneous allocation of rates as a resource allocation problem. We analyze the natural proportional fairness algorithm from economics. To do this, we extend results from market clearing literature, particularly the Eisenberg-Gale markets and the notions of Walrasian equilibria and Gross Substitutes. This yields the first constant competitive algorithm with constant speed augmentation for single-sink flow routing, routing multicast trees, and multidimensional resource allocation with substitutes resources. Next, we consider the general scheduling problem with packing constraints on rates, but with the restriction that the number of different job types is fixed. We model this problem as a non-stochastic queueing problem. We generalize a natural algorithm from queueing literature and analyze it by extending queueing theoretic ideas. We show that the competitive ratio, for any constant speed, depends polynomially only on the number of job types. Further, such a dependence on the number of job types is unavoidable for non-clairvoyant algorithms. This yields the first algorithm for scheduling multicommodity flows whose competitive ratio depends polynomially on the size of the underlying graph, and not on the number of jobs.

Details

SODA Conference 2015 Conference Paper

New Approximations for Broadcast Scheduling via Variants of α-point Rounding

  • Sungjin Im
  • Maxim Sviridenko

We revisit the pull-based broadcast scheduling model. In this model, there are n unit-sized pages of information available at the server. Clients send their requests to the server over time asking for specific pages. The server can transmit only one page at each time. When the server transmits a page, all outstanding requests for the page are simultaneously satisfied, and this is what distinguishes broadcast scheduling from the standard scheduling setting where each job must be processed separately by the server. Broadcast scheduling has received a considerable amount of attention due to the algorithmic challenges that it gives in addition to its applications in multicast systems and wireless and LAN networks. In this paper, we give the following new approximation results for two popular objectives: For the objective of minimizing the maximum flow time, we give the first PTAS. Previously, it was known that the algorithm First-In-First-Out (FIFO) is a 2-approximation, and it is tight [14, 16]. It has been suggested as an open problem to obtain a better approximation [14, 4, 25, 31]. For the objective of maximizing the throughput, we give a 0. 7759-approximation which improves upon the previous best known 0. 75-approximation [23]. Our key techniques for these improvements are novel variants of α-point rounding that can effectively reduce congestion in schedule which is often the main hurdle in designing scheduling algorithms based on linear programming. We believe that our new rounding schemes could be of potential use for other scheduling problems.

Details

FOCS Conference 2015 Conference Paper

Tight Bounds for Online Vector Scheduling

  • Sungjin Im
  • Nathaniel Kell
  • Janardhan Kulkarni
  • Debmalya Panigrahi

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and L r norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and L r -norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations - for all L r norms and in both the identical and unrelated machines settings. Our main results are: · For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general L r norms. · For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general L r norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual L r objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.

Details

STOC Conference 2014 Conference Paper

Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

  • Sungjin Im
  • Janardhan Kulkarni
  • Kamesh Munagala

We introduce and study a general scheduling problem that we term the Packing Scheduling problem (PSP). In this problem, jobs can have different arrival times and sizes; a scheduler can process job j at rate x j , subject to arbitrary packing constraints over the set of rates (x) of the outstanding jobs. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling.

Details

SODA Conference 2014 Conference Paper

New Approximations for Reordering Buffer Management

  • Sungjin Im
  • Benjamin Moseley

In this paper we consider the buffer reordering management problem. In this model there are n elements that arrive over time with different colors. There is a buffer that can store up to k elements and when the buffer becomes full an element must be output. If an element is output that has a color different from the previous element, a cost depending on the color must be paid. This cost could be uniform or non-uniform over colors; these are called unweighted and weighted cases, respectively. The goal is to reorder elements within the buffer before outputting them to minimize the total cost incurred. There has been a search over the last decade to resolve the complexity of this problem online and offline. Very recently, there has been substantial progress for the unweighted case – an O (1)-approximation algorithm and an O (log log k )-competitive randomized algorithm were given [6, 7]. These results resolve the complexity of the unweighted buffer problem, up to constant factors, since the problem is NP-Hard and there is a matching lower bound on the competitive ratio. However, the progress for the weighted case has not been as satisfactory as for the unweighted case. Our main result is a randomized O (loglog kγ )-approximation for the weighted case, which gives an exponential improvement over the previously best known result of O ( y /l ogk ) which assumed γ = poly( k ). Here γ is the ratio of the maximum to minimum weight. We also revisit the unweighted case and give an improved randomized 66. 0823-approximation which improves (modestly) upon the approximation guarantee given in [6]. The algorithm and analysis we use for the unweighted case was done independently of [6]. We believe that our new interpretation of the problem and our analysis of an underlying random process could be of potential use in other settings.

Details

FOCS Conference 2014 Conference Paper

SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors

  • Sungjin Im
  • Janardhan Kulkarni
  • Kamesh Munagala
  • Kirk Pruhs

We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job J has processing length pj, weight wj, and is processed at a rate of lij when scheduled on machine i. The online scheduler knows the values of wj and lij upon arrival of the job, but is not aware of the quantity pj. We present the first online algorithm that is scalable ((1+ε)-speed O(1/2)-competitive for any constant ε > 0) for the total weighted flow-time objective. No non-trivial results were known for this setting, except for the most basic case of identical machines. Our result resolves a major open problem in online scheduling theory. Moreover, we also show that no job needs more than a logarithmic number of migrations. We further extend our result and give a scalable algorithm for the objective of minimizing total weighted flow-time plus energy cost for the case of unrelated machines. In this problem, each machine can be sped up by a factor of f-1i(P) when consuming power P, where fi is an arbitrary strictly convex power function. In particular, we get an O(γ2)-competitive algorithm when all power functions are of form sγ. These are the first non-trivial non-clairvoyant results in any setting with heterogeneous machines. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. This has a spirit similar to coordination mechanisms that attempt to achieve near optimum welfare in the presence of selfish agents (jobs). To the best our knowledge, this is the first work that demonstrates the usefulness of ideas from coordination mechanisms and Nash equilibria for designing and analyzing online algorithms.

Details

SODA Conference 2011 Conference Paper

Secretary Problems: Laminar Matroid and Interval Scheduling

  • Sungjin Im
  • Yajun Wang

The classical secretary problem studies the problem of hiring the best secretary from among the secretaries who arrive in random order by making immediate and irrevocable decisions. After the interesting connection to online mechanism design was found [19, 20], the random order input assumption has been studied for a variety of problems. Babaioff et al. [4] formalized a general version of the secretary problem, namely the matroid secretary problem. In the problem, a secretary corresponds to an element in the universe U. The goal is to select the maximum weight independent set. They conjectured that the matroid secretary problem, for any matroid, allows a constant competitive algorithm. The conjecture remains open. Some constant approximation algorithms are currently known for some special cases of matroids. Another interesting type of secretary problem was studied where elements have non-uniform sizes, as is the case in the knapsack secretary problem [3, 6]. In this paper, we consider two interesting secretary problems. One is when the matroid is a laminar matroid, which generalizes uniform / partition / truncated partition matroids. For the laminar matroid secretary problem, using a novel replacement rule which we call “kick next, ” we give the first constant-competitive algorithm. The other is the interval scheduling secretary problem, which generalizes the knapsack secretary problem. In this problem, each job J i arrives with interval I i, processing time p i and weight w i. If J i is accepted, then it must be scheduled during I i, not necessarily continuously. The goal is to accept the jobs of the maximum total weight which are schedulable. We give a simple O (log D )-competitive algorithm and a nearly matching lower bound on the competitive ratio of any randomized algorithm, where D is the maximum interval length of any job.

Details
v2026.09.13