# Publications & Preprints

No. | Author(s) | Title | Preprint (arXiv) |
Publication (MathSciNet) |
---|---|---|---|---|

2015c01 | Gottschalk, Corinna; Vygen, Jens | Better s-t-tours by Gao trees | 1511.05514 | MR3534727 |

2015c02 | Newman, Alantha; Röglin, Heiko; Seif, Johanna | The alternating stock size problem and the gasoline puzzle | 1511.09259 | MR3550134 |

2015c03 | Singh, Mohit; Zenklusen, Rico | k-trails: recognition, complexity, and approximations | 1512.01781 | MR3534726 |

2015c04 | Fujishige, Satoru; Tanigawa, Shin-ichi | Polynomial combinatorial algorithms for skew-bisubmodular function minimization | ||

2015c05 | Borgwardt, Steffen; De Loera, Jesús A.; Finhold, Elisabeth | The diameters of transportation polytopes satisfy the Hirsch conjecture | 1603.00325 | |

2015c06 | Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Post, Ian | A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs | 1502.04588 | MR3382460 |

2015c07 | Feldmann, Andreas Emil; Könemann, Jochen; Pashkovich, Kanstantsin; Sanità, Laura | Fast approximation algorithms for the generalized survivable network design problem | 1604.07049 | appeared in Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), pp 33:1-33:12, 2016 |

2015c08 | Friggstad, Zachary; Könemann, Jochen; Shadravan, Mohammad | A logarithmic integrality gap bound for directed Steiner tree in quasi-bipartite graphs | 1604.08132 | MR3539190 |

2015c09 | Könemann, Jochen; Pashkovich, Kanstantsin; Toth, Justin | An elementary integrality proof of Rothblum's stable matching formulation | 1605.04427 | MR3573195 |

2015c10 | Sebő, András; van Zuylen, Anke | The salesman's improved paths: a 3/2+1/34 approximation | 1604.02486 | appeared in Proceedings of the 57th Annual Symposium on Foun- dations of Computer Science (FOCS 2016), pp 118-127, 2016 |

2015c11 | Conforti, Michele; Wolsey, Laurence A. | "Facet" separation with one linear program | ||

2015c12 | Mnich, Matthias; Williams, Virginia Vassilevska; Végh, László A. | A 7/3-approximation for feedback vertex sets in tournaments | 1511.01137 | MR3550130 |

2015c13 | Abdi, Ahmad; Cornuéjols, Gérard; Pashkovich, Kanstantsin | Ideal clutters that do not pack | ||

2015c14 | Ahmadian, Sara; Swamy, Chaitanya | Approximation algorithms for clustering problems with lower bounds and outliers | 1608.01700 | |

2015c15 | Fiorini, Samuel; Huynh, Tony; Joret, Gwenaël; Pashkovich, Kanstantsin | Smaller extended formulations for the spanning tree polytope of bounded-genus graphs | 1604.07976 | MR3614780 |

2015c16 | Pashkovich, Kanstantsin | Every rational polyhedron has finite split rank: new proof | 1606.05811 | |

2015c17 | Olver, Neil; Végh, László A. | A simpler and faster strongly polynomial algorithm for generalized flow maximization | 1611.01778 | appeared in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp 100-111, 2017 |

2015c18 | Fortier, Quentin; Király, Csaba; Szigeti, Zoltán; Tanigawa, Shin-ichi | On packing spanning arborescences with matroid constraint | link, pdf | |

2015c19 | Bazzi, Abbas; Fiorini, Samuel; Huang, Sangxia; Svensson, Ola | Small extended formulation for knapsack cover inequalities from monotone circuits | 1609.03737 | appeared in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp 2326-2341, 2017 |

2015c20 | Dadush, Daniel; Regev, Oded | Towards strong reverse Minkowski-type inequalities for lattices | 1606.06913 | |

2015c21 | Dadush, Daniel; Végh, László A.; Zambelli, Giacomo | Rescaling algorithms for linear programming - part I: conic feasibility | 1611.06427 | |

2015c22 | van Zuylen, Anke | Improved approximations for cubic and cubic bipartite TSP | 1507.07121 | appeared in "Integer Programming and Combinatorial Optimization", Lecture Notes in Computer Science, Vol. 9682, pp 250-261 |

2015c23 | Jackson, Bill; Nixon, Anthony | Global rigidity of generic frameworks on concentric cylinders | 1610.07755 | |

2015c24 | Panageas, Ioannis; Piliouras, Georgios | Gradient descent only converges to minimizers: non-isolated critical points and invariant regions | 1605.00405 | to appear in Innovations in Theoretical Computer Science (ITCS), 2017 |

2015c25 | Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V. | Mutation, sexual reproduction and survival in dynamic environments | 1511.01409 | to appear in Innovations in Theoretical Computer Science (ITCS), 2017 |

2015c26 | Chandrasekaran, Karthekeyan; Gottschalk, Corinna; Könemann, Jochen; Peis, Britta; Schmand, Daniel; Wierz, Andreas | Additive stabilizers for unstable graphs | 1608.06797 | |

2015c27 | Annamalai, Chidambaram | Finding perfect matchings in bipartite hypergraphs | 1509.07007 | MR3478502 |

2015c28 | Chakrabarty, Deeparnab; Lee, Yin Tat; Sidford, Aaron; Wong, Sam Chiu-wai | Subquadratic submodular function minimization | 1610.09800 | appeared in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp 1220-1231, 2017 |

2015c29 | Lee, Jon; Skipper, Daphne | Virtuous smoothing for global optimization | 1605.05221 | |

2015c30 | Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio | Scaling, proximity, and optimization of integrally convex functions | 1703.10705 | appeared in Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), pp 57:1-57:13, 2016 |

2015c31 | Connelly, Robert; Gortler, Steven J.; Theran, Louis | Generic global and universal rigidity | 1604.07475 | |

2015c32 | Chekuri, Chandra; Xu, Chao | Computing minimum cuts in hypergraphs | 1607.08682 | appeared in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp 1085-1100, 2017 |

2015c33 | Chekuri, Chandra | Some open problems in element-connectivity | ||

2015c34 | Kaszanitzky, Viktoria E.; Schulze, Bernd; Tanigawa, Shin-ichi | Global rigidity of periodic graphs under fixed-lattice representations | 1612.01379 | |

2015c35 | Arulselvan, Ashwin; Cseh, Ágnes; Groß, Martin; Manlove, David F.; Matuschke, Jannik | Matchings with lower quotas: algorithms and complexity | 1412.0325 | appeared in Algorithmica (2016), pp 1-24 |

2015c36 | Iwamasa, Yuni; Murota, Kazuo; Zivny, Stanislav | Discrete convexity in joint winner property | 1701.07645 | |

2015c37 | Palaiopanos, Gerasimos; Panageas, Ioannis; Piliouras, Georgios | Multiplicative weights update with constant step-size in congestion games: convergence, limit cycles and chaos | 1703.01138 | |

2015c38 | Eftekhari, Yaser; Jackson, Bill; Nixon, Anthony; Schulze, Bernd; Tanigawa, Shin-ichi; Whiteley, Walter | Point-hyperplane frameworks, slider joints, and rigidity preserving transformations | 1703.06844 | |

2015c39 | Abdi, Ahmad; Pashkovich, Kanstantsin | Deltas, delta minors and delta free clutters | ||

2015c40 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph optimization I: branchings and matchings | 1608.05722 | to appear in Mathematics of Operations Research |

2015c41 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph optimization II: matroidal term rank augmentation | 1608.05730 | to appear in Mathematics of Operations Research |

2015c42 | Bérczi, Kristóf; Frank, András | Supermodularity in unweighted graph opitimization III: highly-connected digraphs | 1608.05729 | to appear in Mathematics of Operations Research |

2015c43 | Könemann, Jochen; Olver, Neil; Pashkovich, Kanstantsin; Ravi, Ramamoorthi; Swamy, Chaitanya; Vygen, Jens | On the integrality gap of the prize-collecting Steiner forest LP | 1706.06565 | to appear in APPROX 2017 |

2015c44 | Dadush, Daniel; Végh, László A.; Zambelli, Giacomo | Rescaled coordinate descent methods for linear programming | MR3534719 | |

2015c45 | Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio | Discrete midpoint convexity | 1708.04579 | |

2015c46 | Calinescu, Gruia; Kortsarz, Guy; Nutov, Zeev | Improved approximation algorithms for Minimum Power Covering problems | Preprint |