HOẠT ĐỘNG TRONG TUẦN

Thời gian: 9h30, Thứ 5, ngày 9/5/2019
Địa điểm: Phòng 611- 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt.

Tóm tắt: Sắp xếp trên cây là bài toán tìm cách đưa một hoán vị của các số trên các đỉnh của một cây về một hoán vị khác bằng các phép đổi chỗ hai số của một cạnh sao cho số phép đổi chỗ là ít nhất. Bài toán này đã được quan tâm tìm hiểu trên các lớp đồ thị khác nhau từ gần 30 năm nay. Trong trường hợp đồ thị tổng quát, bài toán là NP- đầy đủ. Trong trường hợp đồ thị là đường thẳng bài toán là tuyến tính, dựa trên số các phép nghịch thế của hoán vị thông thường. Giữa hai lớp đồ thị này gần như chưa có kết quả có tính xây dựng nào. Sự phức tạp của bài toán là một thay đổi nhỏ về cấu trúc đồ thị có thể dẫn đến một thay đổi lớn về tính gần đúng của các thuật toán đã được đề xuất.

Câu hỏi mở là bài toán Sắp xếp trên cây thuộc lớp NP- đầy đủ hay lớp P?

Trong seminar này, chúng tôi sẽ trình bày một số kết quả vừa công bố tháng 3/2019 của nhóm 9 tác giả (Biniaz et al.) về bài toán này, trong đó có việc phủ định giả thuyết "Chiếc lá hạnh phúc" ( Vaughan, 1991) và việc tìm ra giới hạn xấp xỉ cho một số thuật toán gần đúng. Ngoài ra chúng tôi cũng sẽ trình bày một số ý tưởng của chúng tôi (cùng với Christophe Durr và Christophe Crespelle) trong việc mở rộng khái niệm nghịch thế từ Hoán vị (trên đường thẳng) lên cây.