Bài toán thư ký là một bài toán nổi tiếng trong lý thuyết dừng tối ưu. Bài toán này đã được nghiên cứu trong xác suất ứng dụng, thống kê, và lý thuyết quyết định.Dạng cơ bản của bài toán là như sau. Một người quản lý cần tuyển thư ký tốt nhất trong n ứng viên có thể xếp hạng. Các ứng viên được phỏng vấn lần lượt theo một thứ tự ngẫu nhiên. Quyết định cho mỗi ứng viên phải được đưa ra ngay sau khi phỏng vấn ứng viên đó. Sau khi đã bị từ chối, ứng viên đó sẽ không thể được tuyển. Trong quá trình phỏng vấn, người quản lý có thể xếp hạng các ứng viên đã phỏng vấn nhưng không biết gì về chất lượng của các ứng viên chưa phỏng vấn. Câu hỏi đặt ra là nên sử dụng chiến thuật nào để tối ưu hóa xác suất tuyển được ứng viên tốt nhất.Bài toán cơ bản trên có một lời giải đẹp. Đầu tiên phỏng vấn và từ chối khoảng n/e ứng viên (trong đó e là cơ số của lôgarit tự nhiên). Sau đó chấp nhận ứng viên đầu tiên tốt hơn tất cả các ứng viên đã được phỏng vấn trước đó (hoặc chấp nhận ứng viên cuối cùng nếu điều này không xảy ra). Nếu áp dụng thuật toán này thì xác suất tuyển được ứng viên tốt nhất là khoảng 1/e và đây cũng là xác suất tối ưu.