[ Universität Bonn | Institut für Informatik | Abteilung V | english version ]

Richard Schmied Institut für Informatik und Hausdorff Center for Mathematics, HCM Universität Bonn Friedrich-Ebert-Allee 144 53113 Bonn Email:  schmied followed by at cs.uni-bonn.de Telefon: +49 228 734209 Fax: +49 228 734440

Veröffentlichungen

• Approximation Hardness of Graphic TSP on Cubic Graphs
  Joint work with Marek Karpinski,
  CS-Report 85338, 2013 (ps, pdf).
  


• New Inapproximability Bounds for TSP
  Joint work with Marek Karpinski and Michael Lampis,
  CoRR abs/1303.6437, 2013 (ps, pdf).
  


• On Improved Inapproximability Results for the Shortest Superstring and Related Problems
  Joint work with Marek Karpinski
  In Proc. 19th CATS (2013), CRPIT 141, pp. 27-36, 2013 (ps,pdf).
  


• On Approximation Lower Bounds for TSP with bounded Metrics
  Joint work with Marek Karpinski,
  CoRR abs/1201.5821, 2012 (ps,pdf).
  


• Improved Lower Bounds for the Shortest Superstring and Related Problems
  Joint work with Marek Karpinski,
  CoRR abs/1111.5442, 2011 (ps,pdf).
  


• Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs
  Joint work with Marek Karpinski and Claus Viehamnn,
  ECCC TR11-098, 2011 (ps,pdf).
  


• Approximability of Vertex Cover in Dense Bipartite Hypergraphs
  Joint work with Jean Cardinal, Marek Karpinski, and Claus Viehmann
  CS-Report 85319, 2011 (ps,pdf).


• Approximating Vertex Cover in Dense Hypergraphs,
  Joint work with Jean Cardinal, Marek Karpinski, and Claus Viehmann,
  in Journal of Discrete Algorithms 13, pp. 67-77, 2012 (ps,pdf).
  


• Approximating Edge Dominating Set in Dense Graphs
  Joint work with Claus Viehmann,
  Proc. 8th TAMC (2011), LNCS 6648, pp. 37-47;
  also in Theoretical Computer Science 414, pp. 92-99, 2012 (ps,pdf).
  


• Approximating Subdense Instances of Covering Problems
  Joint work with Jean Cardinal, Marek Karpinski, and Claus Viehmann,
  Proc. 6th LAGOS (2011), pp. 59-65;
  also in Electronic Notes in Discrete Mathematics 37, pp. 297-302, 2011 (ps,pdf).
  


• On Approximation Complexity of Metric Dimension Problem
  Joint work with Mathias Hauptmann and Claus Viehmann,
  In Proc. 21st IWOCA (2010), LNCS 6460, pp. 136-139, 2011;
  also in Journal of Discrete Algorithms 14, pp. 214-220, 2012 (ps,pdf).
  


• On Approximation Complexity of Edge Dominating Set Problem in Dense Graphs
  Joint work with Claus Viehmann,
  Proc. 7th JCCGG 2009, pp. 135-136.
  


• Polynomial Approximation Schemes for Dense and Geometric k-Restricted Steiner Forest Problems
  Joint work with Mathias Hauptmann, Sören Kühl, and Claus Viehmann,
  CS-Report 85288, 2008 (ps,pdf).

Talks

• On Approximability of Bounded Degree Instances of Selected Optimization Problems
  ( slides), Bonn, July 25, 2013