演講公告
新聞標題: ( 2024-03-15 )
演講主題:Obtaining Approximately Optimal and Diverse Solutions via Dispersion
主講人:蔡詩妤博士(中央研究院資訊科學研究所)
演講日期:2024年3月26日(二) 14:00 –15:00
演講地點:(光復校區) 科學一館223室
摘要內容:
Abstract. We study diverse solutions to optimization problems and design fair scheduling of demands with different priorities on wireless networks The problem of finding several sufficiently-diverse, yet approximately-optimal solutions to an optimization problem can be described as follows: given an integer k, an approximation factor $\alpha$, and a diversity measure $\sigma$ on a set of solutions to an optimization problem P, find a set of k solutions to P that (a) are all $\alpha$ approximately-optimal for P and (b) maximize the diversity measure $\sigma$ over all such sets of k solutions. The optimization problems considered here are maximum matching, spanning tree, global min-cut, shortest path, and minimum weight bases of a matroid. Here, a solution is a set of edges, and the number of edges two given solutions differ in as the diversity measure of the pair. The diversity measure $\sigma$ of k solutions is the sum of the pairwise Hamming distance between the bit-vectors representing the k solutions. We propose the first polynomial-time algorithms that (except for the unweighted spanning tree), for these five graph problems, guarantee that their diversity is at least 1/4 times the optimal diversity under different $\alpha$.
This result is applied for minimum weight bases of a matroid, which means it gives us diverse $\alpha$-approximate minimum spanning trees, advancing a step towards achieving diverse $\alpha$-approximate TSP tours.相關檔案:Talk_1130326.pdf