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?

  • 6
    $\begingroup$ 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. $\endgroup$ Commented Dec 17, 2010 at 4:19
  • 2
    $\begingroup$ I can imagine what the difference is, but let's wait for the definitions. $\endgroup$
    – Raphael
    Commented Dec 17, 2010 at 10:20

1 Answer 1


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.

  • $\begingroup$ Ok, thanks for the reference! Indeed my definition is wrong, and actually incremental optimization is more general than online optimization. $\endgroup$ Commented Dec 21, 2010 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.