<p>Thanks.</p>

<p>With Garmow's comment I was able to find the first two references which also called on-line algorithms as on-line:</p>

<p><a href="https://www.sciencedirect.com/science/article/pii/S0022000074800267" rel="nofollow noreferrer">Johnson, David S. "Fast algorithms for bin packing." Journal of Computer and System Sciences 8.3 (1974): 272-314.</a></p>

<p>and</p>

<p><a href="https://dspace.mit.edu/bitstream/handle/1721.1/57819/17595570-MIT.pdf?sequence=2" rel="nofollow noreferrer">Johnson, David S. Near-optimal bin packing algorithms. Diss. Massachusetts Institute of Technology, 1973.</a></p>

CC BY-SA 3.0
2018-02-13T14:37:48.800Z
2018-02-13T14:37:48.800Z
kombinatorix
<p>I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the one that was the original reference.</p>

<p>Note: English is my second language.</p>

CC BY-SA 3.0
2018-02-13T13:52:49.920Z
Get a copy of [Borodin and El-Yaniv's text](https://scholar.google.com/scholar?cluster=7726049700429222225&hl=en&as_sdt=0,22) on online algorithms.  The [first page of their preface](https://books.google.com/books?hl=en&lr=&id=v3faI8pER6IC&oi=fnd&pg=PR13&ots=A7x3GKSO3T&sig=lZG0cIhY16KF8K5dHvU_NzQGwxo#v=onepage&q&f=false) discusses the history.  They mention Graham's analysis of the online greedy algorithm for scheduling jobs on identical processors, and the analysis of self-adjusting data structures (e.g. list management)
Neal Young
CC BY-SA 3.0
2018-02-13T14:05:04.567Z
Section 3(Historical Background) of https://link.springer.com/chapter/10.1007%2FBFb0029562 contains some historical remarks.
Gamow
<reference-request><ho.history-overview><online-algorithms>
Searching for the original definition of online algorithms
kombinatorix
# Searching for the original definition of online algorithms

(Asked by: username_0 on 2018-02-13)

I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the one that was the original reference.

Note: English is my second language.

**Tags:** reference-request, ho.history-overview, online-algorithms

> **Comments:**
> **username_1**: Get a copy of [Borodin and El-Yaniv's text](https://scholar.google.com/scholar?cluster=7726049700429222225&hl=en&as_sdt=0,22) on online algorithms.  The [first page of their preface](https://books.google.com/books?hl=en&lr=&id=v3faI8pER6IC&oi=fnd&pg=PR13&ots=A7x3GKSO3T&sig=lZG0cIhY16KF8K5dHvU_NzQGwxo#v=onepage&q&f=false) discusses the history.  They mention Graham's analysis of the online greedy algorithm for scheduling jobs on identical processors, and the analysis of self-adjusting data structures (e.g. list management)  
> **username_2**: Section 3(Historical Background) of https://link.springer.com/chapter/10.1007%2FBFb0029562 contains some historical remarks.  

---

## 1 answers

### Answer by username_0 on 2018-02-13. Score: 2 | Accepted answer

Thanks.

With Garmow's comment I was able to find the first two references which also called on-line algorithms as on-line:

[Johnson, David S. "Fast algorithms for bin packing." Journal of Computer and System Sciences 8.3 (1974): 272-314.](https://www.sciencedirect.com/science/article/pii/S0022000074800267)

and

[Johnson, David S. Near-optimal bin packing algorithms. Diss. Massachusetts Institute of Technology, 1973.](https://dspace.mit.edu/bitstream/handle/1721.1/57819/17595570-MIT.pdf?sequence=2)


---

