New lower and upper bounds for the competitive ratio of transmission protocols.
Maciej LiskiewiczBodo MantheyPublished in: Inf. Process. Lett. (2004)
Keyphrases
- lower and upper bounds
- competitive ratio
- lower bound
- upper bound
- branch and bound algorithm
- branch and bound
- online algorithms
- single machine
- data transmission
- np hard
- worst case
- lagrangian relaxation
- processing times
- average case
- valid inequalities
- objective function
- sample complexity
- cutting plane
- sufficient conditions
- data sets
- search algorithm
- convergence rate