Archive for the ‘2017’ Category

Euiwoong Lee (이의웅), FPT Approximation Algorithms for Graph Problems

Friday, June 9th, 2017
FPT Approximation Algorithms for Graph Problems
Euiwoong Lee (이의웅)
Computer Science Department, Carnegie Mellon University
2017/07/06 Thu 4PM-5PM
Approximation algorithms and fixed-parameter tractable (FPT) algorithms have been two major ways to deal with NP-hardness of combinatorial optimization problems. The notion of FPT approximation can be naturally defined, and it is getting significant attention recently. Starting from gentle introductions to approximation algorithms and FPT algorithms, I will talk about my three recent results on FPT approximability.
– Given a graph G = (V, E) and an integer k, we study k-Vertex Separator, where the goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most k vertices. We give an O(log k)-FPT approximation algorithm for k-Vertex Separator. Our result improves the best previous graph partitioning algorithms.
– We also study k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. We present an O(log k)-FPT approximation algorithm for k-Path Transversal. There was no nontrivial approximation algorithm for k > 4 before this work.
– Finally, k-cut is the problem where we want to remove the minimum number of edges such that the graph has at least k connected components. We give a (2 – ε)-FPT approximation algorithm for some epsilon > 0, improving upon a (non-FPT) 2-approximation.
The third result is joint work with Anupam Gupta and Jason Li.

Changhyun Kwon (권창현), On the Price of Satisficing in Network User Equilibria

Thursday, June 8th, 2017
On the Price of Satisficing in Network User Equilibria
Changhyun Kwon (권창현)
Industrial and Management Systems Engineering, University of South Florida
2017/07/10 Mon 4PM-5PM
When network users are satisficing decision-makers, the resulting traffic pattern attains a satisficing user equilibrium, which may deviate from the (perfectly rational) user equilibrium. In a satisficing user equilibrium traffic pattern, the total system travel time can be worse than in the case of the PRUE. We show how bad the worst-case satisficing user equilibrium traffic pattern can be, compared to the perfectly rational user equilibrium. We call the ratio between the total system travel times of the two traffic patterns the price of satisficing, for which we provide an analytical bound. Using the sensitivity analysis for variational inequalities, we propose a numerical method to quantify the price of satisficing for any given network instance.

(Distinguished Lecture) Terence Tao, The Erdős discrepancy problem

Monday, June 5th, 2017

(FYI: 2017 CMC Distinguished Lecture Series)

The Erdős discrepancy problem
Terence Tao
Department of Mathematics, UCLA
2017/06/15 4PM (Fusion Hall, KI Bldg.)
The discrepancy of a sequence f(1), f(2), … of numbers is defined to be the largest value of |f(d) + f(2d) + … + f(nd)| as n,d range over the natural numbers. In the 1930s, Erdős posed the question of whether any sequence consisting only of +1 and -1 could have bounded discrepancy. In 2010, the collaborative Polymath5 project showed (among other things) that the problem could be effectively reduced to a problem involving completely multiplicative sequences. Finally, using recent breakthroughs in the asymptotics of completely multiplicative sequences by Matomaki and Radziwill, as well as a surprising application of the Shannon entropy inequalities, the Erdős discrepancy problem was solved in 2015. In this talk I will discuss this solution and its connection to the Chowla and Elliott conjectures in number theory.

Henry Liu, Highly connected subgraphs in sparse graphs

Sunday, June 4th, 2017
Highly connected subgraphs in sparse graphs
Henry Liu
Central South University, Changsha, China
2017/6/15 Thu 2PM-3PM
Let G be a graph on n vertices with independence number α. How large must a k-connected subgraph G contain? We shall present the best possible answers when α=2 and α=3. Some open questions will also be presented.
Joint work with Shinya Fujita (Yokohama City University, Japan) and Amites Sarkar (Western Washington University, USA).

O-joung Kwon (권오정), On low rank-width colorings

Sunday, May 14th, 2017
On low rank-width colorings
O-joung Kwon (권오정)
Technische Universitat Berlin, Berin, Germany
2017/6/09 Friday 11AM
We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [Grad and classes with bounded expansion I. Decompositions. EJC 2008]. We say that a class ? of graphs admits low rank-width colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, every graph G∈? can be vertex colored with at most N(p) colors such that the union of any i≤p color classes induces a subgraph of rank-width at most Q(i).
Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class ? of bounded expansion and every positive integer r, the class {Gr: G∈?} of r-th powers of graphs from ?, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. In this talk, we provide the color refinement technique necessary to show the first result. This is joint work with Sebastian Sierbertz and Michał Pilipczuk.