All reports by Author Gerhard J. Woeginger:

__
TR01-085
| 1st October 2001
__

Gerhard J. Woeginger#### Resource augmentation for online bounded space bin packing

__
TR01-084
| 1st October 2001
__

Gerhard J. Woeginger#### When does a dynamic programming formulation guarantee the existence of an FPTAS?

__
TR00-050
| 13th July 2000
__

Peter Auer, Philip M. Long, Gerhard J. Woeginger#### On the Complexity of Function Learning

Gerhard J. Woeginger

We study online bounded space bin packing in the resource

augmentation model of competitive analysis.

In this model, the online bounded space packing algorithm has

to pack a list L of items in (0,1] into a small number of

bins of size b>=1.

Its performance is measured by comparing the ...
more >>>

Gerhard J. Woeginger

We derive results of the following flavor:

If a combinatorial optimization problem can be formulated via a dynamic

program of a certain structure and if the involved cost and transition

functions satisfy certain arithmetical and structural conditions, then

the optimization problem automatically possesses a fully polynomial time

approximation scheme (FPTAS).

Peter Auer, Philip M. Long, Gerhard J. Woeginger

The majority of results in computational learning theory

are concerned with concept learning, i.e. with the special

case of function learning for classes of functions

with range {0,1}. Much less is known about the theory of

learning functions with a larger range such

as N or R. In ...
more >>>