Home
Â
Shai Gutner's home page
I completed my Ph.D. in Computer Science at the Tel-Aviv University under the supervision of Prof. Noga Alon and Prof. Yossi Azar.
E-mail: shai.gutner@cs.tau.ac.il
Major interests
Online and Approximation Algorithms
Pseudorandomness and Derandomization
Parameterized Complexity
Graph Choosability
Papers published
N. Alon and S. Gutner, Balanced hashing, color coding and approximate counting,
S. Gutner, Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor,
S. Gutner and M. Tarsi, Some results on (a:b)-choosability,
S. Gutner, Elementary approximation algorithms for prize collecting Steiner tree problems,
N. Alon and S. Gutner, Linear time algorithms for finding a dominating set of fixed size in degenerated graphs,
N. Alon and S. Gutner, Balanced families of perfect hash functions and their applications,
Also: ACM Transactions on Algorithms, to appear.
Y. Azar, I. Gamzu and S. Gutner, Truthful unsplittable flow for large capacity networks,
Also: ACM Transactions on Algorithms, to appear.
N. Alon, Y. Azar and S. Gutner, Admission control to minimize rejections and online set cover with repetitions,
S. Gutner, The complexity of planar graph choosability,
Theses
S. Gutner, Algorithms for optimization problems on networks and graphs,
Ph.D. thesis, Tel-Aviv University, 2009. [ps] [pdf] [Hebrew doc] [Hebrew pdf]
S. Gutner, Choice numbers of graphs,