3 papers
cs.DS2026
On Randomized Online Span Minimization
Adrian Calinescu, Gruia Calinescu, Peng-Jun Wan
We study the online Busy Time scheduling model on a single machine of unbounded capacity, with non-preemptive jobs. In our setting, flexible jobs arrive online with a processing ti…
cs.DS2023
An Improved Algorithm for Finding Maximum Outerplanar Subgraphs
Gruia Calinescu, Hemanshu Kaul, Bahareh Kudarzi
We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2/3. We propose a new approximation algorithm which i…
cs.DS2017
An FPTAS of Minimizing Total Weighted Completion Time on Single Machine with Position Constraint
G. Calinescu, F. Jaehn, M. Li +1
In this paper we study the classical scheduling problem of minimizing the total weighted completion time on a single machine with the constraint that one specific job must be sched…