Zobrazeno 1 - 10
of 170
pro vyhledávání: '"Im, Sungjin"'
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 correspondin
Externí odkaz:
http://arxiv.org/abs/2409.03020
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 collec
Externí odkaz:
http://arxiv.org/abs/2405.07949
Autor:
Bhaskara, Aditya, Gollapudi, Sreenivas, Im, Sungjin, Kollias, Kostas, Munagala, Kamesh, Sankar, Govind S.
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 participatio
Externí odkaz:
http://arxiv.org/abs/2401.13053
Datalogo 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
Externí odkaz:
http://arxiv.org/abs/2312.14063
The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is $\frac{e}{e-1}$-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large varian
Externí odkaz:
http://arxiv.org/abs/2308.05067
We revisit the online dynamic acknowledgment problem. In the problem, a sequence of requests arrive over time to be acknowledged, and all outstanding requests can be satisfied simultaneously by one acknowledgement. The goal of the problem is to minim
Externí odkaz:
http://arxiv.org/abs/2305.18227
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 possibl
Externí odkaz:
http://arxiv.org/abs/2212.07682
Autor:
Im, Sungjin, Li, Shi
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
Externí odkaz:
http://arxiv.org/abs/2211.10398
We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based
Externí odkaz:
http://arxiv.org/abs/2211.08381