|
02/03, Goran Konjevod, Department of CSE, Compacting cuts: a new linear formulation for minimum cut
Abstract:
For a graph $(V,E)$, existing compact linear formulations for the
minimum cut problem require $\Theta(|V||E|)$ variables and constraints
and can be interpreted as a composition of $|V|-1$ polyhedra for the
minimum $s$-$t$ cuts in much the same way as early approaches to
finding globally minimum cuts relied on $|V|-1$ calls to a minimum
$s$-$t$ cut algorithm. We present the first formulation to beat this
bound: one which has only $O(|V|^2)$ variables and $O(|V|^3)$
constraints. Our result implies a relaxation for the $k$-edge
connected spanning subgraph problem with $O(|V|^2)$ constraints and
$O(|V|^3)$ variables that is as strong as the standard cut-based
relaxation.
Joint work with R. D. Carr (Sandia), G. Little (MIT), V. Natarajan (CMU)
and O. Parekh (Emory).
|
|
02/17, Toni Farley, Department of CSE, Multiterminal Resilience on Series-Parallel Graphs.
Abstract: Network resilience measures the average 2-terminal
reliability (connectedness) of a graph. Multiterminal resilience
extends this measure to any k vertices; it is the average k-terminal
reliability of a graph. Calculating multiterminal resilience on
general graphs encompasses all-terminal reliability and thus is
NP-hard. I will consider multiterminal resilience on series-parallel
graphs, and present an efficient (O(n2) time) algorithm for
calculating the resilience for any k.
|
|
02/24, Guoliang Xue, Department of CSE, Multiconstrained Quality of Service Routing
Abstract: A fundamental problem in quality-of-service (QoS) routing is to find a path
between a specified source-destination node pair that satisfies K additive
QoS constraints, where K>=2 is a constant integer. This problem is known to
be NP-complete. For the case where K=2, several versions of FPTAS are known.
We concentrate on the general problem where K is any constant greater than
or equal to 2.
We first present a very simple K-approximation algorithm that can be used
in hop-by-hop routing, with a time complexity essentially the same as that
for computing a shortest path. We then make use of this K-approximation
algorithm to design a fully polynomial time approximation scheme (FPTAS).
When reduced to the case of K=2, our FPTAS has a better running time than
the current best FPTAS.
Bio of Speaker:
Guoliang (Larry) Xue is a Professor of Computer Science and Engineering at
Arizona State University. He received the PhD degree in Computer Science
from the University of Minnesota in 1991. He has held previous positions
as Assistant Professor/Associate Professor of Computer Science at the
University of Vermont. His research interests are in networking and
bioinformatics. He currently serves on the editorial boards of IEEE Network,
Computer Networks, and IEEE Transactions on Circuits and Systems-I.
|
|
03/24, Vikram Kamat, Department of Mathematics and Statistics, Two new bijections on lattice paths
Abstract: Let $S_n=\{s_1\ldots s_{2n}|s_i\in \{-1,+1\}\}.$ For $S\in S_n$, let
$\sigma(S)=(\sigma_1,\ldots,\sigma_{2n})$, where
$\sigma_i=\sum_{j=1}^is_j.$ We say $S$ is positive if all
$\sigma_i>0$. Let $P_n$ be all positive sequences in $S_n.$ It is
known that $|P_n|=\binom{2n-1}{n}$ and several bijective proofs
exist. I will present two new bijective proofs for this result, one
using an indirect bijection and the other, a direct one. This is a
joint work with Glenn Hurlbert and Chris Severs, Arizona State
University.
|
|
04/07, Sriram Penumatcha, Department of Mathematics and Statistics.
Abstract: TBA.
|
|
04/14, Andrzej Czygrinow, Distributed algorithms in sparse networks, Department of Mathematics and Statistics.
Abstract: TBA.
|
|
04/21, Justie Su-tzu Juan, National Chi Nan University.
Abstract: TBA.
|
|
|
