Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: New Competitive Analysis Results of Online List Scheduling Algorithm   Online algorithm has been an emerging area of interest for researchers in
various domains of computer science. The online $m$-machine list scheduling
problem introduced by Graham has gained theoretical as well as practical
significance in the development of competitive analysis as a performance
measure for online algorithms. In this paper, we study and explore the
performance of Graham's online \textit{list scheduling algorithm(LSA)} for
independent jobs. In the literature, \textit{LSA} has already been proved to be
$2-\frac{1}{m}$ competitive, where $m$ is the number of machines. We present
two new upper bound results on competitive analysis of \textit{LSA}. We obtain
upper bounds on the competitive ratio of $2-\frac{2}{m}$ and
$2-\frac{m^2-m+1}{m^2}$ respectively for practically significant two special
classes of input job sequences. Our analytical results can motivate the
practitioners to design improved competitive online algorithms for the
$m$-machine list scheduling problem by characterization of real life input
sequences.

6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
15
The categories of this paper are: nucl-ex
26
The categories of this paper are: bayes-an
12
The categories of this paper are: nucl-th
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
14
The categories of this paper are: math-ph
22
The categories of this paper are: chao-dyn
17
The categories of this paper are: q-fin
7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
31
The categories of this paper are: ao-sci