LuanVan.vnLuận Văn
Gửi thư

Empirical Approach to The Complexity of Hard Problems

Luận án · Tiến sĩ · năm 2005 · đề tài tham khảo

Loại tài liệuLuận án
Bậc họcTiến sĩ
NgànhCông nghệ thông tin
Tác giảEugene Nudelman
Cơ sở đào tạoĐại học Quốc gia TP. Hồ Chí Minh
Năm2005
NguồnThư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc

Tóm tắt

Traditionally, computer scientists have considered computational problems and al¬gorithms as artificial formal objects that can be studied theoretically. In this work we propose a different view of algorithms as natural phenomena that can be studied using empirical methods. In the first part, we propose a methodology for using ma-chine learning techniques to create accurate statistical models of running times of a given algorithm on particular problem instances. Rather than focus on the traditional aggregate notions of hardness, such as worst-case or average-case complexity, these models provide a much more comprehensive picture of algorithms' performance. We demonstrate that such models can indeed be constructed for two notoriously hard domains: winner determination problem for combinatorial auctions and satisfiability of Boolean formulae. In both cases the models can be analyzed to shed light on the characteristics of these problems that make them hard. We also demonstrate two con¬crete applications of empirical hardness models. First, these models can be used to construct efficient algorithm portfolios that select correct algorithm on a per-instance basis. Second. the models can be used to induce harder benchmarks. In the second part of this work we take a more traditional view of an algorithm as a tool for studying the underlying problem. We consider a very challenging problem of finding a sample Nash equilibrium (NE) of a normal-form game. For this domain, we first present a novel benchmark suite that is more representative of the problem than traditionally-used random games. We also present a very simple search algorithm for finding NEs. The simplicity of that algorithm allows us to draw interesting conclusions about the underlying nature of the problem based on its empirical performance. In particular. we conclude that most structured games of interest have either pure-strategy equilibria or equilibria with very small supports.
Bản toàn văn lưu tại thư viện Đại học Quốc gia TP. Hồ Chí Minh

Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.

Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
  • Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
  • Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
  • Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.

Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.

Đề tài cùng ngành

Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.