<p>This is discussed in section 2.2.3 of Jeffrey Hartline's thesis: <a href="http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf">http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf</a></p>

<p>Online problems are all about informational uncertainty: you don't know what inputs are coming tomorrow, and the difficulty is often information theoretic, not computational. On the other hand, there is no uncertainty in an incremental optimization problem as Hartline defines it: every parameter of the problem is known at the outset. Without computational restrictions, the problems can always be solved optimally.</p>

<p>So perhaps your definition is wrong, since indeed yours sounds like an online problem. The problem of "incremental optimization" seems to be defined in this 2008 thesis, and differs from your definition in that there is no uncertainty.</p>

CC BY-SA 2.5
2010-12-21T05:36:54.900Z
Ok, thanks for the reference! Indeed my definition is wrong, and actually incremental optimization is more general than online optimization.
Murilo de Lima
CC BY-SA 2.5
2010-12-20T21:38:38.383Z
2010-12-20T21:38:38.383Z
Aaron Roth
<p>Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every online problem as an incremental counterpart (the reverse is clearly true).</p>

<p>Here go the (not very formal) definitions. In an incremental problem, one is given a sequence of instances of an optimization problem. The (i+1)-th instance is an "extension" of the i-th one. The (i+1)-th solution must be calculated without knowledge of the "future" instances, and has to keep the decisions made at the i-th solution. The classical example is with the k-median problem: after opening k facilities, one wants to have k' > k facilities but does not want to demolish the old ones.</p>

<p>In an online problem, (the usual definition is that) one is given a sequence of "requests". Here, one also has to answer a request without knowledge of the future requests. One wants to optimize the cost/gain of answering the sequence as a whole.</p>

<p>I believe that for any online problem I can define an "offline" optimization problem that fits the incremental definition (and what I usually see is the reverse). If the definitions are equivalent, what is the point of using a different name for the same concept?</p>

CC BY-SA 2.5
2010-12-17T04:19:37.957Z
Can you provide the definitions of incremental and online optimization problems? (by pressing the edit button above) This will make the question self-contained and help the community to understand your problem, which increases the possibility of the question being answered.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-17T10:20:42.450Z
I can imagine what the difference is, but let's wait for the definitions.
Raphael
<ds.algorithms><optimization><online-algorithms>
What's the difference between online and incremental optimization?
Murilo de Lima
# What's the difference between online and incremental optimization?

(Asked by: username_0 on 2010-12-17)

Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every online problem as an incremental counterpart (the reverse is clearly true).

Here go the (not very formal) definitions. In an incremental problem, one is given a sequence of instances of an optimization problem. The (i+1)-th instance is an "extension" of the i-th one. The (i+1)-th solution must be calculated without knowledge of the "future" instances, and has to keep the decisions made at the i-th solution. The classical example is with the k-median problem: after opening k facilities, one wants to have k' > k facilities but does not want to demolish the old ones.

In an online problem, (the usual definition is that) one is given a sequence of "requests". Here, one also has to answer a request without knowledge of the future requests. One wants to optimize the cost/gain of answering the sequence as a whole.

I believe that for any online problem I can define an "offline" optimization problem that fits the incremental definition (and what I usually see is the reverse). If the definitions are equivalent, what is the point of using a different name for the same concept?

**Tags:** ds.algorithms, optimization, online-algorithms
> **Comments:**
> **username_1**: Can you provide the definitions of incremental and online optimization problems? (by pressing the edit button above) This will make the question self-contained and help the community to understand your problem, which increases the possibility of the question being answered.  
> **username_2**: I can imagine what the difference is, but let's wait for the definitions.  

---

## 1 answers

### Answer by username_3 on 2010-12-20. Score: 12 | Accepted answer

This is discussed in section 2.2.3 of Jeffrey Hartline's thesis: <http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf>

Online problems are all about informational uncertainty: you don't know what inputs are coming tomorrow, and the difficulty is often information theoretic, not computational. On the other hand, there is no uncertainty in an incremental optimization problem as Hartline defines it: every parameter of the problem is known at the outset. Without computational restrictions, the problems can always be solved optimally.

So perhaps your definition is wrong, since indeed yours sounds like an online problem. The problem of "incremental optimization" seems to be defined in this 2008 thesis, and differs from your definition in that there is no uncertainty.

> **Comments:**
> **username_0**: Ok, thanks for the reference! Indeed my definition is wrong, and actually incremental optimization is more general than online optimization.  

---

