[Colloquium] [Staff] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

THEORY SEMINAR
Date:         Tuesday, October 9,  2012
Time:        3 p.m.
Place:        Ryerson 251, 1100 E. 58th Street
_________________________ 

Speaker:    Parinya Chalermsook
From:        IDSIA, Switzerland
Title: 	Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f(GxH) where G and H are graphs, "x" is a graph product and f is a graph property. For example, if f is the independence number and "x" is the disjunctive product, then it is a simple exercise to check that f(GxH)=f(G)f(H).
In this paper, we study graph products in the following non-standard form: f((GxH)&J) where G, H and J are graphs, x and & are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some graph products "x" and "&", it is subadditive in the sense that f((GxH)&J) <= f(G&J)+f(H&J). Moreover, when function f is the poset dimension number, it is "almost subadditive".

As applications of this result (we only need J=K_2 here), we obtain nearly tight hardness of approximation results for many optimization problems in discrete mathematics and computer science: bipartite induced matching, poset dimension, maximum expanding sequences, maximum feasible subsystem with 0/1 coefficients, profit-maximization pricing (in various settings), boxicity, cubicity, threshold dimension, donation center location, and independent packing.

This work will appear in SODA 2013 (Joint work with Bundit Laekhanukit and Danupon Nanongkai)

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20121009/32607f96/attachment.htm