# Selected Publications of former Research Area K

[K:HCS11] S. Held, W. Cook, and E. Sewell. Safe lower bounds for graph coloring. In Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 261–273. Springer, 2011.

[K:Kou11] S. Hougardy. On packing squares into a rectangle. Computational Geometry, 44:456–463, 2011.

[K:MRV11] D. Müller, K. Radke, and J. Vygen. Faster min-max resource sharing in theory and practice. Mathematical Programming Computation, 3:1–35, 2011.

[K:BHM+10] C. Bartoschek, S. Held, J. Maßberg, D. Rautenbach, and J. Vygen. The repeater tree construction problem. Information Processing Letters, 110:1079–1083, 2010.

[K:BKZ10] P. Berman, M. Karpinski, and A. Zelikovsky. A 3/2-approximation algorithm for generalized Steiner tree problems in graphs with edge length 1 and 2. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), pages 15–24. Springer, 2010.

[K:CLV09] W. J. Cook, L. Lovász, and J. Vygen, editors. Research Trends in Combinatorial Optimization. Springer, 2009.

[K:PRV09] S. Peyer, D. Rautenbach, and J. Vygen. A generalization of Dijkstra’s shortest path algorithm with applications to VLSI routing. Journal of Discrete Algorithms, 7:377–390, 2009.

[K:Bre08] U. Brenner. A faster polynomial algorithm for the unbalanced Hitchcock transportation problem. Operations Research Letters, 36:408–413, 2008.

[K:BSV08] U. Brenner, M. Struzyna, and J. Vygen. BonnPlace: Placement of leading-edge chips by advanced combinatorial algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27:1607–1620, 2008.

[K:KV08] B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, fourth edition, 2008. (translations into German 2008, Japanese 2009, French 2010, Italian 2011, Chinese forthcoming, Russian forthcoming).

[K:K:MV08] J. Maßberg and J. Vygen. Approximation algorithms for a facility location problem with service capacities. ACM Transactions of Algorithms, 4, 2008. Article 50.

[K:KRV07] B. Korte, D. Rautenbach, and J. Vygen. BonnTools: Mathematical innovation for layout and timing closure of systems on a chip. Proceedings of the IEEE, 95:555–572, 2007.

[K:Vyg07] J. Vygen. From stars to comets: Improved local search for universal facility location. Operations Research Letters, 35:427–433, 2007.

[K:WRS07] J. Werber, D. Rautenbach, and C. Szegedy. Timing optimization by restructuring long combinatorial paths. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 536–543. IEEE, 2007.

# Selected Publications of former Research Area L

[L:GKa] S. Geschke and M. Kojman. Symmetrized induced Ramsey theorems. Graphs and Combinatorics. DOI:10.1007/s00373-010-1006-x, to appear.

[L:GKb] M. Gitik and P. Koepke. Violating the singular cardinals hypothesis without large cardinals. Israel Journal of Mathematics. to appear.

[L:IKRS] G. Ivanyos, M. Karpinski, L. Rónyai, and N. Saxena. Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Mathematics of Computation. DOI:10.1090/S0025-5718-2011-02505-6, to appear.

[L:FG11] S. Frick and S. Geschke. Basis theorems for continuous n-colorings. Journal of Combinatorial Theory A, 118:1334–1349, 2011.

[L:SS11] N. Saxena and C. Seshadhri. An almost optimal rank bound for depth-3 identities. SIAM Journal on Computing, 40:200–224, 2011.

[L:CKKS10] M. Cramer, P. Koepke, D. Kühlwein, and B. Schröder. Premise selection in the Naproche system. In Proceedings of the 5th International Joint Conference on Automated Reasoning (IJCAR), pages 434–440. Springer, 2010.

[L:GJK10] L. A. Goldberg, M. Jerrum, and M. Karpinski. The mixing time of Glauber dynamics for coloring regular trees. Random Structures and Algorithms, 36:464–476, 2010.

[L:IKS10] G. Ivanyos, M. Karpinski, and N. Saxena. Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal on Computing, 39:3736–3751, 2010.

[L:KRS10] M. Karpinski, A. Rucinski, and E. Szymanska. The complexity of perfect matching problems on dense hypergraphs. International Journal of Foundations of Computer Science, 21:905–924, 2010.

[L:KS10] M. Karpinski and W. Schudy. Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC), pages 3–14. Springer, 2010.

[L:KAF+10] T. Kleinjung, K. Aoki, J. Franke, A. Lenstra, E. Thome, J. Bos, P. Gaudry, A. Kruppa, P. Montgomery, D. Osvik, H. te Riele, A. Timofeev, and P. Zimmermann. Factorization of a 768-bit RSA modulus. In Proceedings of the 30th Annual Cryptology Conference (CRYPTO), pages 333–350. Springer, 2010.

[L:IKS09] G. Ivanyos, M. Karpinski, and N. Saxena. Schemes for deterministic polynomial factoring. In Proceedings of the 34th International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 191–198. Springer, 2009.

[L:KS09] M. Karpinski and W. Schudy. Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pages 626–636, 2009.

[L:Koe09] P. Koepke. Ordinal computability. In Proceedings of the 5th Conference on Computability in Europe (CiE), pages 280–289. Springer, 2009.

[L:KS09] P. Koepke and B. Seyfferth. Ordinal machines and admissible recursion theory. Annals of Pure and Applied Logic, 160:310–318, 2009.

[L:BKS07] P. Berman, M. Karpinski, and A. Scott. Computational complexity of some restricted instances of 3SAT. Discrete Applied Mathematics, 155:649–653, 2007.