3 citations · 3 across the 6 of their papers we have counts for
7 papers
Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
Adrian Calinescu, Gruia Calinescu
Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We ca…
Busy Time Minimization with Preemption, Migration, and One Resource Requirement
Gruia Calinescu, Mozhengfu Liu
We study the Busy Machine Time with Preemption and Migration and One Resource Requirement problem, motivated by energy minimization in cloud data centers. Given unlimited identical…
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…
Online Flexible Busy Time Scheduling on Heterogeneous Machines
Gruia Calinescu, Adrian Calinescu, Sami Davies +2
We study the online busy time scheduling model on heterogeneous machines. In our setting, jobs with uniform processing time arrive online with a deadline that becomes known to the…
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…
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…
1.85 Approximation for Min-Power Strong Connectivity
Gruia Calinescu
Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H…