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 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 pdf MR3844535
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 MR3598412
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 MR3630972
2015c11 Conforti, Michele; Wolsey, Laurence A. "Facet" separation with one linear program pdf MR4019954
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 pdf  
2015c14 Ahmadian, Sara; Swamy, Chaitanya Approximation algorithms for clustering problems with lower bounds and outliers 1608.01700 MR3577130
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 MR3678174
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 MR3885413
2015c20 Dadush, Daniel; Regev, Oded Towards strong reverse Minkowski-type inequalities for lattices 1606.06913 MR3631007
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 MR3865720
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 MR3754926
2015c25 Mehta, Ruta; Panageas, Ioannis; Piliouras, Georgios; Tetali, Prasad; Vazirani, Vijay V. Mutation, sexual reproduction and survival in dynamic environments 1511.01409 MR3754940
2015c26 Chandrasekaran, Karthekeyan; Gottschalk, Corinna; Könemann, Jochen; Peis, Britta; Schmand, Daniel; Wierz, Andreas Additive stabilizers for unstable graphs 1608.06797 MR3927009
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 MR3678265
2015c29 Lee, Jon; Skipper, Daphne Virtuous smoothing for global optimization 1605.05221 MR3714557
2015c30 Moriguchi, Satoko; Murota, Kazuo; Tamura, Akihisa; Tardella, Fabio Scaling, proximity, and optimization of integrally convex functions 1703.10705 MR39428885
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 MR3627799
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 MR3741541
2015c36 Iwamasa, Yuni; Murota, Kazuo; Zivny, Stanislav Discrete convexity in joint winner property 1701.07645 MR3799038
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 MR3926261
2015c39 Abdi, Ahmad; Pashkovich, Kanstantsin Deltas, delta minors and delta free clutters pdf  
2015c40 Bérczi, Kristóf; Frank, András Supermodularity in unweighted graph optimization I: branchings and matchings 1608.05722 MR3846069
2015c41 Bérczi, Kristóf; Frank, András Supermodularity in unweighted graph optimization II: matroidal term rank augmentation 1608.05730 MR3846070
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 MR3695584
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 MR4018001