流程 
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 kHub Center Problem is to find adepth2 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 kHub 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 nonhubs. Both
Star
kHub Center Problem and Single Allocation kHub Center Problem
are NPhard and have applications in transportation system,
telecommunication system, and post mail system. In this talk, I
will
give 5/3approximation algorithms for both problems. Moreover,
I
will give a proof to show that for any 0 , the Star kHub Center
Problem has no ( 1.5 )approximation algorithm unless P =
NP. Under the assumption P ≠ NP, for any 0 the Single
Allocation kHub 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 costsharing games,
where the set of Nash equilibria depends fundamentally on the
choice of an edge costsharing 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 costsharing
protocols for undirected and directed graphs, singlesink and
multicommodity networks, different classes of costsharing
methods, and different measures of the inefficiency of equilibria.
One of our main technical tools is a complete characterization
of the
uniform costsharing protocolsprotocols 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 bestpossible
performance of nonuniform costsharing protocols.
15:30~16:30
Talk 3
The backup 2center problem
Speaker:台北商業大學資訊與決策科學研究所王弘倫副教授
Abstract
The backup 2center 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 2center problem on a tree.
