Campus Event Calendar
Event Entry
What and Who
An Approximate König's Theorem for Edge-Coloring Weighted Bipartite Graphs
Jose R. Correa
School of Business, Universidad Adolfo Ibanez, Chile
Talk
AG 1, AG 2, AG 3
Expert Audience
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 9 February 2005
14:00
60 Minutes
46.1 - MPII
024
Saarbrücken
Abstract
We consider a generalization of edge coloring bipartite graphs in
which every edge has a weight in $[0,1]$ and the coloring of the edges
must satisfy that the sum of the weights of the edges incident to a
vertex $v$ of any color must be at most 1. For unit weights, K\"onig's
theorem says that the number of colors needed is exactly the maximum
degree. For this generalization, we show that $2.557 n + o(n)$ colors
are sufficient where $n$ is the maximum total weight adjacent to any
vertex, improving the previously best bound of $2.833n+O(1)$ due to Du
et al. This question is motivated by the question of the
rearrangeability of 3-stage Clos networks. In that context, the
corresponding parameter $n$ of interest in the edge coloring problem
is the maximum over all vertices of the number of unit-sized bins
needed to pack the weights of the incident edges. In that setting, we
are able to improve the bound to $2.5480n + o(n)$, also improving a
bound of $2.5625n+O(1)$ of Du et al. Additionally, we look at the
online variant of the problem, in which edges are revealed over time.
Using heuristics borrowed from online bin packing we obtain, among
other results, a bound of $5n$ for the online coloring problem,
improving upon the $5.75n$ of Gao and Hwang. The latter result leads
to a simple $O(n\log n)$ algorithm for the offline problem that is
guaranteed to use no more than $8n/3$ colors.
Our analysis is interesting in its own and involves a novel
decomposition result for bipartite graphs and the introduction of
an associated continuous one-dimensional bin packing instance which
we can prove allows perfect packing.
This is joint work with Michel Goemans
which every edge has a weight in $[0,1]$ and the coloring of the edges
must satisfy that the sum of the weights of the edges incident to a
vertex $v$ of any color must be at most 1. For unit weights, K\"onig's
theorem says that the number of colors needed is exactly the maximum
degree. For this generalization, we show that $2.557 n + o(n)$ colors
are sufficient where $n$ is the maximum total weight adjacent to any
vertex, improving the previously best bound of $2.833n+O(1)$ due to Du
et al. This question is motivated by the question of the
rearrangeability of 3-stage Clos networks. In that context, the
corresponding parameter $n$ of interest in the edge coloring problem
is the maximum over all vertices of the number of unit-sized bins
needed to pack the weights of the incident edges. In that setting, we
are able to improve the bound to $2.5480n + o(n)$, also improving a
bound of $2.5625n+O(1)$ of Du et al. Additionally, we look at the
online variant of the problem, in which edges are revealed over time.
Using heuristics borrowed from online bin packing we obtain, among
other results, a bound of $5n$ for the online coloring problem,
improving upon the $5.75n$ of Gao and Hwang. The latter result leads
to a simple $O(n\log n)$ algorithm for the offline problem that is
guaranteed to use no more than $8n/3$ colors.
Our analysis is interesting in its own and involves a novel
decomposition result for bipartite graphs and the introduction of
an associated continuous one-dimensional bin packing instance which
we can prove allows perfect packing.
This is joint work with Michel Goemans
Contact
Ellen Fries
9325 502
--email hidden
passcode not visible
logged in users only
Ellen Fries, 01/31/2005 12:46
Ellen Fries, 01/25/2005 11:04 -- Created document.
Ellen Fries, 01/25/2005 11:04 -- Created document.