BỘ KHOA HỌC VÀ CÔNG NGHỆ
HỆ THỐNG THÔNG TIN KHOA HỌC VÀ CÔNG NGHỆ

Các nhiệm vụ khác
liên kết website
Lượt truy cập
 Lượt truy cập :  15,258,432
  • Kết quả thực hiện nhiệm vụ

101.01-2016.08

2019-52-991/KQNC

Thuật toán hiệu quả cho bài toán vị trí ngược

Trường Đại Học Cần Thơ

Bộ Giáo dục và Đào tạo

Quốc gia

TS. Nguyễn Trung Kiên

TS. Nguyễn Thư Hương; TS. Nguyễn Thanh Hùng;

Toán học ứng dụng

01/04/2017

01/04/2019

2019

Cần Thơ

96 tr.

Tìm thuật toán hữu hiệu với thời gian tính toán đa thức để giải các bài toán ngược 1-median hoặc 1-center trên đồ thị đoạn. Chứng minh một số bài toán vị trí ngược 1-median có thứ tự với hàm mục tiêu không lồi là NP-khó hoặc tìm ra thuật toán hữu hiệu để giải quyết chúng. Bài toán sẽ được nghiên cứu trên các lớp đồ thị cây và chu trình. Tìm hiểu về tính chất của bài toán vị trí trí ngược với ràng buộc cắt-và-lắp. Qua đó, tìm các thuật toán đa thức để giải các bài toán này trên các lớp đồ thị khác nhau.

 

Bài toán ngược; Đồ thị đoạn; Thuật toán hữu hiệu; Đẳng thức; Qui hoạch tuyến tính

24 Lý Thường Kiệt, Hà Nội

16551