Publications & Preprints

No. Author(s) Title Preprint
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  
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 pdf  
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  
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 The power of locality: an elementary integrality proof of Rothblum's stable matching formulation 1605.04427  
2015c10 Sebő, András; van Zuylen, Anke The salesman's improved paths: 3/2+1/34 integrality gap and approximation ratio 1604.02486  
2015c11 Conforti, Michele; Wolsey, Laurence A. "Facet" separation with one linear program pdf  
2015c12 Mnich, Matthias; Williams, Virginia Vassilevska; Végh, László A. A 7/3-approximation for feedback vertex sets in tournaments 1511.01137  
2015c13 Abdi, Ahmad; Cornuéjols, Gérard; Pashkovich, Kanstantsin Ideal clutters that do not pack pdf  
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  
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  
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  
2015c28 Chakrabarty, Deeparnab; Lee, Yin Tat; Sidford, Aaron; Wong, Sam Chiu-wai Subquadratic submodular function minimization 1610.09800  
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 27th International Symposium on Algorithms and Computation (ISAAC 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 64 (2016), pp 57:1-57:13
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 to appear in SODA 2017
2015c33 Chekuri, Chandra Some open problems in element-connectivity pdf  
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 pdf