Daniel Page

Mr. Daniel Page


Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 June 2020 in Theoretical Computer Science
Verified
Journal Article
Closed access
DPDaniel Page
Daniel Page
RSRoberto Solis-Oba
Roberto Solis-Oba

20 July 2012 in Journal of Mathematical Modelling and Algorithms in Operations Research
Verified
Journal Article
Closed access
PDF file
DPDaniel Page
Daniel Page

8 June 2016 in Algorithms
Verified
Journal Article
Open access
PDF file
DPDaniel Page
Daniel Page
RSRoberto Solis-Oba
Roberto Solis-Oba
In the pursuit of finding subclasses of the makespan minimization problem on unrelated parallel machines that have approximation algorithms with approximation ratio better than 2, the graph balancing problem has been of current interest. In the graph balancing problem each job can be non-preemptively scheduled on one of at most two machines with the same processing time on either machine. Recently, Ebenlendr, Krčál, and Sgall (Algorithmica 2014, 68, 62–80.) presented a 7 / 4 -approximation algorithm for the graph balancing problem. Let r , s ∈ Z + . In this paper we consider the graph balancing problem with two weights, where a job either takes r time units or s time units. We present a 3 / 2 -approximation algorithm for this problem. This is an improvement over the previously best-known approximation algorithm for the problem with approximation ratio 1.652 and it matches the best known inapproximability bound for it.

1 February 2020 in Theoretical Computer Science
Verified
Journal Article
Closed access
DPDaniel Page
Daniel Page
RSRoberto Solis-Oba
Roberto Solis-Oba
MMMarten Maack
Marten Maack

31 January 2015 in SOP Transactions on Applied Mathematics
Verified
Journal Article
Closed access
PDF file
DPDaniel Page
Daniel Page
Let there be m parallel machines and n jobs, where a job j can be scheduled on machine i to take pi, j ∈ Z+ time units. The makespan Cmax is the completion time of a machine that finishes last. The goal is to produce a schedule with all n jobs that has minimum makespan. This is the makespan problem on unrelated parallel machines, denoted as R||Cmax. Assume p,q ∈ Z+ are constants, let A(p,q) = {a ∈ Z+ | p ≤ a ≤ q}. We explore a general NP-hard subclass of R||Cmax when processing times are between p and q inclusive or pi,j=∞ abbreviated as R|pi,j ∈ A(p,q)∪{∞}|Cmax, where pi,j = ∞ means job j cannot be scheduled to machine i. We give a (q/p)-approximation algorithm for R|pi,j ∈ A(p,q)∪{∞}|Cmax. As a consequence, we obtain a 2-approximation algorithm for the NP-hard subclass R||Cmax with job lengths 1, 2, or pi,j=∞. In addition, we prove R||Cmax with job lengths 1, 2, and 3 is NP-hard, and present a 3/2-approximation algorithm for this subclass of R||Cmax.