|
|
Siamak Tazari's Publications
My primary research interests are algorithmic graph
structure theory and algorithm
engineering. Recently, I have also started working
in algorithmic game theory.
I am interested in understanding and exploiting the
structure of certain graph classes to obtain better
and faster algorithms. These classes include
planar graphs, bounded genus graphs,
minor-closed graph classes and their further
generalizations. One of the main goals of this
research is to identify the largest classes of graphs
on which (a lot of) problems are still tractable in
some sense. The tractability notions of interest to me
are that of parameterized complexity and
approximation schemes .
-
While there have been vast advances in the
development of efficient algorithms in the past few
decades - be it in the realm of approximations or that
of parameterized complexity, a large number of these
algorithms seem to be impractical due to their huge
hidden constants or dependence on the parameter. One of
my main interests is to extract the practical
content of deep theoretical results,
engineer it, and make it applicable in real world
contexts.
-
On the topic of algorithmic game theory, I am
interested in combinatorial games with an underlying
graph structure and would like to understand the case
when we restrict the game to certain graph classes, such
as planar graphs. In particular, I am studying network
creation games, cost-sharing schemes, and truthful
mechanism design in this context.
Here you find my recent online
publications, conference
papers, journal
articles, academic theses and
manuscripts, and previous
projects.
- Directed Nowhere Dense Classes of Graphs
with Stephan Kreutzer.
Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA'12), Kyoto, Japan, to appear, 2012.
( long version)
- Lower Bounds for the
Complexity of Monadic Second-Order Logic
with Stephan Kreutzer.
Proceedings of the 25th IEEE symposium on Logic in Computer Science
(LICS'10) , Edinburgh, Scotland, UK, pp. 189-198, 2010.
( long version)
- On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
with Stephan Kreutzer.
Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms
(SODA'10) , Austin, Texas, USA, pp. 354-364, 2010.
( long version)
- Faster
Approximation Schemes and Parameterized Algorithms on H-Minor-Free and
Odd-Minor-Free Graphs
Proceedings of the 35th international symposium on Mathematical
Foundations of Computer Science (MFCS'10), Brno, Czech Republic,
LNCS 6281, pp. 641-652, 2010.
( long version)
- Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
with Glencora Borradaile and Erik
D. Demaine. Proceedings of the 26th
International Symposium on Theoretical Aspects of Computer Science
(STACS'09), Freiburg, Germany, pp. 171-182, 2009.
( long version)
- Dealing with Large Hidden Constants: Engineering a Planar Steiner Tree PTAS
with Matthias
Müller-Hannemann. Proceedings of the 11th Workshop on Algorithm
Engineering and Experiments (ALENEX'09), New York, USA, pp. 120-131,
SIAM, 2009.( journal version)
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
with Matthias
Müller-Hannemann. Proceedings of the 34th Workshop on Graph
Theoretic Concepts in Computer Science (WG'08), Durham, UK, LNCS
5344, pp. 360-371, Springer, 2008.( journal version)
- A Near Linear Time Approximation Scheme for Steiner Tree among Obstacles in the Plane
with Matthias
Müller-Hannemann. Proceedings of the 10th Workshop on Algorithms
and Data Structures (WADS'07), Halifax, Canada, LNCS 4619, pp. 151-162, 2007. ( journal version)
- Workload Balancing in Multi-Stage Production Processes
with Matthias
Müller-Hannemann and Karsten Weihe. Proceedings of the 5th
Int. Workshop on Experimental Algorithms (WEA'06), Menorca, Spain, LNCS 4007, pp. 49-60, 2006.(see Diploma thesis)
|
Journal Articles
- Computing Hypergraph Width Measures Exactly
with Lukas Moll and Marc Thurley.
Information Processing Letters, accepted for publication, 2011.
( preprint)
- Faster
Approximation Schemes and Parameterized Algorithms on (odd-)H-Minor-Free Graphs
Theoretical Computer Science, special issue on MFCS'10, in press, doi:10.1016/j.tcs.2011.09.014, 2011.
- Dealing with Large Hidden Constants: Engineering a Planar Steiner Tree PTAS
with Matthias
Müller-Hannemann. ACM Journal of Experimental Algorithmics 16 (3), special issue on ALENEX'09, Article 3.16, 2011.
- A Near
Linear Time Approximation Scheme for Steiner Tree among Obstacles in
the Plane
with Matthias
Müller-Hannemann. Computational Geometry: Theory and
Applications 43 (4), special issue on WADS'07,
pp. 395-409, doi:10.1016/j.comgeo.2009.01.011, 2010.
- Shortest Paths in Linear Time on Minor-Closed Graph Classes, with an Application to Steiner Tree Approximation
with Matthias
Müller-Hannemann. Discrete Applied Mathematics 157,
pp. 673-684, doi:10.1016/j.dam.2008.08.002, 2009.
|
Academic Theses and Manuscripts
-
Algorithmic Graph Minor Theory: Approximation, Parameterized
Complexity, and Practical Aspects
Doctoral Dissertation,
Humboldt-Universität zu Berlin, Berlin,
Germany, July 2010.
- Bidimensionality
Theory and Algorithmic Graph Minor Theory
with Mareike Massow, Jens Schmidt, and Daria
Schymura. Lecture Notes of MohammadTaghi Hajiaghayi's Tutorial in the Fall
School on Algorithmic Graph Structure Theory, Schloss Blankensee, Germany,
2007.
-
Algorithmic Approaches for Two Fundamental Optimization Problems:
Workload-Balancing and Planar Steiner Trees
Diploma Thesis, Technische Universität
Darmstadt, Darmstadt, Germany, August 2006.
- Cross-Monotonic Cost-Sharing Schemes for Combinatorial Optimization Games: A Survey
Course Project, CPSC 532A Multiagent Systems, University of British Columbia, Vancouver, Canada, 2005.
- Applying, Improving and Analyzing Some Heuristics for Binary Codes in Combinatorial DNA Design
with Lyndon Hiew. Course Project, CPSC 545 Mini-Workshop Algorithms for Bioinformatics, University of British Columbia, Vancouver, Canada, 2005.
- A Java Optimizer for the Fast Component Mounter (FCM 2)
Technical Report, Technische
Universität Darmstadt, Germany, May 2003.
|
Previous Projects
- Approximation Algorithms for the Steiner Tree and Related Network
Design Problems with Industry Applications
Funded by the Deutsche Forschungsgemeinschaft (DFG), 2006-2008.
- Optimizing PC Board Assembly Line Throughput
In cooperation with Philips/Assembléon, Eindhoven, Netherlands, 2003-2006.
|
|