演算法與計算理論學會

Association of Algorithm and Computation Theory

研討會訊息公告

主題
Network Optimization Seminar
主辦單位
演算法與計算理論學會
協辦單位
成功大學資訊工程學系
時間
2016年12月5日(一)13:30~16:30
地點
成功大學資訊工程學系4263 教室
流程

13:30~14:30
Talk 1
Approximation algorithms and inapproximability
of hub allocation problems
Speaker: 成功大學資訊工程學系謝孫源特聘教授兼系主任
Abstract
Given a metric graph G = (V, E, w), a center c V , and an integer k, the Star k-Hub Center Problem is to find adepth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. A similar problem called the Single Allocation k-Hub Center Problem is to find a spanning subgraph H* of G such that (i) C* is a clique of size k in H*; (ii) V \ C * forms an independent set in H*; (iii) each v V \ C * is adjacent to exactly one vertex in C*; and (iv) the diameter D(H*) is minimized. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. Both Star k-Hub Center Problem and Single Allocation k-Hub Center Problem are NP-hard and have applications in transportation system, telecommunication system, and post mail system. In this talk, I will give 5/3-approximation algorithms for both problems. Moreover, I will give a proof to show that for any 0 , the Star k-Hub Center Problem has no ( 1.5 )-approximation algorithm unless P = NP. Under the assumption P ≠ NP, for any 0 the Single Allocation k-Hub Center Problem has no ( 4/ 3 )-approximation algorithm.

 

14:30~15:30
Talk 2
Designing Networks With Good Equilibria
Speaker:台灣大學電機工程學系陳和麟副教授
Abstract
In a network with selfish users, designing and deploying a protocol determines the rules of the game by which end users interact with each other and with the network. We study the problem
of designing a protocol to optimize the equilibrium behavior of the induced network game. We consider network cost-sharing games, where the set of Nash equilibria depends fundamentally on the choice of an edge cost-sharing protocol. Previous research focused on the Shapley protocol, in which the cost of each edge is shared equally among its users.
In this talk, we will describe the design of optimal cost-sharing protocols for undirected and directed graphs, single-sink and multicommodity networks, different classes of cost-sharing
methods, and different measures of the inefficiency of equilibria.
One of our main technical tools is a complete characterization of the uniform cost-sharing protocolsprotocols that are designed without foreknowledge of or assumptions on the network in which they will be deployed. We use this characterization result to identify the
optimal uniform protocol in several scenarios. We also provide several matching upper and lower bounds on the best-possible performance of non-uniform cost-sharing protocols.


15:30~16:30
Talk 3
The backup 2-center problem
Speaker:台北商業大學資訊與決策科學研究所王弘倫副教授
Abstract
The backup 2-center problem is a center facility location problem, in which one is asked to deploy two facilities, with a given probability to fail, in a graph. Given that the two facilities do not fail simultaneously, the goal is to find two locations, possibly on edges, that minimize the expected value of the maximum of the distances from all vertices to their closest functioning facility. In this talk, we focus on the algorithmic results of this problem. In particular, we will briefly review the algorithm for computing the center of a tree, and then show how this idea is applied to solve the backup 2-center problem on a tree.