Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Suppose you repeat this every day, and every day the bus arrives a random time between "now" and in (let's say) 30 minutes.

There is a strategy that allows you to never be worse than 2x if you knew exactly when the bus arrived: Wait for 10 minutes, and if the bus didn't arrive, walk home.

In all cases when the bus arrives between now and in 10 minutes, you do the optimal thing, and whenever the bus arrives after 10 minutes have passed, you will be home after 20 minutes, which is not worse than 2x worse than optimal.



Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: