14th Networks - day
On Tuesday June 21tst, the 14th NETWORKS-day is organized by Jop Briët, Stella Kapodistria and Suman Chakraborty. This will be an on-site event for all members and affiliated members.
Programme
| 09.30-09.45 | Opening |
| 09.45-10.45 | Krystal Guo |
| 10.45-11.00 | Coffee break |
| 11.00-12.00 | Pim van der Hoorn |
| 12.00-13.30 | Lunch |
| 13.00-14.00 | Introduction of new Networks members (tentative) |
| 14.00-15.00 | Dion Gijswijt |
| 15.00-15.15 | Coffee break |
| 15.15-16.15 | Royi Jacobovic |
| 16.15-?? | Social |
Abstracts
Speaker: Krystal Guo
Title: Transversal polynomial of graphs.
Abstract: We explore the interplay between algebraic combinatorics and some algorithmic problems in graph theory. We define a polynomial with connections to correspondence colouring, a recent generalization of list-colouring, and the Unique Games Conjecture. Like the chromatic polynomial of a graph, we are able to evaluate this polynomial at -r+1 modulo r^n, despite the complexity of computing this polynomial. This is based on joint work with Chris Godsil and Gordon Royle.
Speaker: Pim van der Hoorn.
Speaker: Dion Gijswijt
Title: Constructing tree decompositions for graphs of bounded gonality.
Abstract: Divisorial gonality is a graph parameter that has its origins in algebraic geometry. It is a combinatorial analogue and lower bound for gonality of algebraic curves. In terms of the classical chip-firing game of Björner-Lovász-Shor it relates to chip configurations that result in a finite game, even after adding a chip at an arbitrary position. In this talk we will show that gonality is an upper bound for the treewidth. Moreover, we give an algorithmic proof that produces a tree-decomposition of width equal to the gonality. We will conclude with some open problems. Joint work with: Hans Bodlaender, Josse van Dobben de Bruyn, and Harry Smit.
Speaker: Royi Jacobovic
Title: Externalities in queues as stochastic processes: The case of M/G/1.
Abstract: Externalities are the costs that a user of a common resource imposes on others. For example, consider a FCFS M/G/1 queue and a customer with service demand of x>=0 minutes who arrived into the system when the workload level was u>=0 minutes. Let E_v(x) be the total waiting time which could be saved if this customer gave up on his service demand. In this work, we analyse the externalities process {E_v(x); x>=0}. The analysis includes a decomposition which yields several results: Convexity of E_v(.), an exact expression for the auto-covariance and a Gaussian approximation of E_v(.). Finally, we also consider the extended framework when is a general nonnegative random variable which is independent from the arrival process and the service demands. This leads to a generalization of an existing result from a previous work of Haviv and Ritov (1998).
This is based on joint work with Michel Mandjes.
If you have any questions please feel free to contact:
Jop Briet (J.Briet@cwi.nl)
Suman Chakraborty (s.chakraborty1@tue.nl)
Stella Kapodistria (S.Kapodistria@tue.nl)
