Implement online algorithms
- Dominant language
- Hy
- Stars
- 2
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
Create implementations for online algorithms:
## Online algorithm paradigms:
- Competitive analysis framework
- Adversarial models
- Randomized online algorithms
- Resource augmentation
## Classic online problems:
- Ski rental problem
- Secretary problem
- k-server problem
- Paging (cache replacement)
- Online scheduling
- Online bin packing
- Online matching
## Applications:
- Resource allocation
- Job scheduling
- Network routing
- Financial algorithms
- Memory management
## Requirements:
- Provide competitive ratio analysis
- Include lower bound proofs
- Create adversarial test cases
- Document practical applications
This collection will demonstrate algorithms that must make decisions with partial information, without knowledge of future inputs, which is essential in many real-time systems and reactive environments.
Contributor guide
Assessment
This issue has not been assessed yet.