bipartite-matching

You are currently browsing articles tagged bipartite-matching.

Tháng 3 và tháng 4 không có quá nhiều điều thú vị, nên mình tổng hợp cả 2 tháng vào một bài.

  1. Tập bài giảng mới của Tim Roughgarden về lý thuyết trò chơi và độ phức tạp. Tập bài giảng này tổng hợp những phát triển lý thuyết mới trong vòng vài năm gần đây về độ phức tạp của tính điểm cân bằng Nash. https://agtb.wordpress.com/2018/03/16/barbados-lectures-on-complexity-theory-game-theory-and-economics/
  2. Giải thuật đấu thầu cho bài toán cặp ghép trong đồ thị hai phía. Mặc dù giải thuật được phát triển đã lâu nhưng giờ mình mới biết đến. Một giải thuật rất đẹp, mình đã viết lại bằng tiếng Việt tại đây. https://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/
  3. Bài giảng của Mikkel Thorup về sức mạnh của phép băm. Băm là một trong những lý thuyết rất đẹp, ứng dụng của băm thì không thể đếm được. Trong blog này có ít nhất 5-7 bài viết liên quan đến băm. Cái khó nhất của lý thuyết băm là thiết kế hàm băm. Trong bài giảng này, Thorup giới thiệu tabulation hashing và sức mạnh của phép băm này https://www.youtube.com/watch?v=c0Wqc0VaF44&t=1376s.
  4. Một bài báo trong ngành vật lý có hơn 5000 tác giả. WTH??? https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.114.191803
  5. Sắc số của mặt phẳng. Đây là một bài toán rất khó. Aubrey de Grey chứng minh rằng sắc số của mặt phẳng ít nhất là 5. Kết quả của Aubrey de Grey cho thấy sắc số của mặt phẳng là một trong 3 số: 5,6,7. Xem report tại blog của Gil: https://gilkalai.wordpress.com/2018/04/10/aubrey-de-grey-the-chromatic-number-of-the-plane-is-at-least-5/
  6. Làm thết nào để ước lượng xác suất một sự kiện xảy ra? Post của Aaronson đề cập tới các công cụ hay sử dụng để ước lượng xác suất. Xem thêm bài mà mình viết về 5 công cụ xác suất. https://www.scottaaronson.com/blog/?p=3712
  7. Một survey mới khá đầy đủ về Bloom Filters. https://arxiv.org/abs/1804.04777
  8. Không gian nhiều chiều có những tính chất vô cùng lạ. Ví dụ khi số chiều càng cao thì thể tích của hình cầu bán kính 1 tiến tới 0. Xem thêm trong chuỗi bài của Gil về sự lạ lùng của không gian nhiều chiều. https://gilkalai.wordpress.com/2018/04/15/test-your-intuition-34-tiling-high-dimensional-spaces-with-two-dimensional-tiles/
  9. Một essay rất đáng đọc và sâu sắc của Michael Jordan về cái gọi là cơn sốt AI. Jordan chỉ ra hai hướng mà chúng ta cần tập trung giải quyết: IA (Intelligence Augmentation) và II (Intelligent Infrastructure) hơn là Juman-imitative AI. https://medium.com/@mijordan3/artificial-intelligence-the-revolution-hasnt-happened-yet-5e1d5812e1e7
  10. Tháng 2 mình đã liên kết tới một breakthrough mới trong lý thuyết độ phức tạp tính toán: Khot, Minzer và Safra đã chứng minh 2-to-2 conjecture là đúng. Quanta Magazine mới có bài viết về ý nghĩa của các kết quả này. https://www.quantamagazine.org/computer-scientists-close-in-on-unique-games-conjecture-proof-20180424/

Tags: , , , , , , ,

« Older entries