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

On the design and worst-case analysis of certain interactive and approximation algorithms

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

Loại tài liệuLuận án
Bậc họcTiến sĩ
Tác giảJia Mao
Cơ sở đào tạoĐại học Quốc gia TP. Hồ Chí Minh
Năm2006
NguồnThư viện số Đại học Quốc gia TP. Hồ Chí Minh · trang gốc

Tóm tắt

With the speed of current technological changes, computation models are evolving to become more interactive and dynamic. These computation models often differ from traditional ones in that not every piece of the information needed for decision making is available a priori. Efficient algorithm design to solve these problems poses new challenges. In this work we present and study some interactive and dynamic computations and design efficient algorithmic schemes to solve them. Our approach for performance evaluation falls within the framework of worst-case analysis. The worst-case scenarios are analyzed through the incorporation of imaginary adversaries or adversarial input sequences. Worst-case analysis provides safe performance guarantees even when we have little or no prior knowledge about the input sequences. An-other natural yet powerful tool we utilize is an auxiliary graph which evolves as the computation progresses. It helps us to visualize the computation step by step, and more importantly, offers us powerful mathematical tools from the well-developed area of graph theory. We first address a particular computation problem of interactive nature, best known as the Majority/Plurality game. This interactive game has appeared in several different contexts since the 1980s such as system diagnosis and group testing. We design and analyze optimal strategies to minimize the amount of communication needed in different settings against an imaginary adversary. We also consider error-tolerance features to make our strategies robust even in the presence of communication errors. We then introduce a new variant of the classical bin packing problem that al-lows arbitrary splitting of the items with the restriction on the number of different types in each bin. This problem is specifically motivated by a practical problem of allocating memories to parallel processors in high-speed routers. It is also natural to other similar resource allocation applications. Even the simplest case of this problem can be shown to be NP-hard. We design efficient approximation algorithms in the offline, online, and dynamic settings. We also use an interesting --improvement technique to show improved approximation ratios.
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.

Đề 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.