Combinatorial Optimization Submissions  2018
December 2018
Approximation Algorithms
An LPbased approximation algorithm for the coveringtype kviolation linear program
Yotaro Takazawa, Shinji Mizuno, Tomonari Kitahara
Approximation Algorithms
Approximate Positive Correlated Distributions and Approximation Algorithms for Doptimal Design
Mohit Singh, Weijun Xie
Approximation Algorithms
A class of spectral bounds for Max kcut
Miguel F. Anjos, José Neto
January 2018
Polyhedra
Facets from Gadgets
Adam N. Letchford, Anh N. Vu
Other
Iterative weighted thresholding method for sparse solution of underdetermined linear equations
Wenxing Zhu, Zilin Huang, Jianli Chen, Zheng Peng
Polyhedra
Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization
Andreas Bärmann, Thorsten Gellermann, Maximilian Merkert, Oskar Schneider
Graphs and Matroids
The Clique Problem with MultipleChoice Constraints under a CycleFree Dependency Graph
Andreas Bärmann, Patrick Gemander, Maximilian Merkert
Other
A polynomial time algorithm for the linearization problem of the QSPP and its applications
Renata Sotirov, Hu Hao
A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations
Marcel de Carli Silva, Levent Tunçel
March 2018
Branch and Cut Algorithms
A new formulation for the Hamiltonian pmedian problem
Tolga Bektaş, Luís Gouveia, Daniel Santos
Branch and Cut Algorithms
Exploring the Numerics of BranchandCut for Mixed Integer Linear Optimization
Matthias Miltenberger, Ted Ralphs, Dan Steffy
Approximation Algorithms for Doptimal Design
Mohit Singh, Weijun Xie
Branch and Cut Algorithms
Computing the Spark: MixedInteger Programming for the (Vector) Matroid Girth Problem
Andreas M. Tillmann
Other
On the Consistent Path Problem
Leonardo Lozano, David Bergman, Cole Smith
April 2018
Polyhedra
Parity Polytopes and Binarization
Dominik Ermel, Matthias Walter
Improving the linear relaxation of maximum $k$cut with semidefinitebased constraints
Vilmar Jefté Rodrigues de Sousa, Miguel F. Anjos, Sébastien Le Digabel
Approximation Algorithms
A linear bound on the integrality gap for SumUp Rounding in the presence of vanishing constraints
Paul Manns, Christian Kirches, Felix Lenders
May 2018
An Improved Flowbased Formulation and Reduction Principles for the Minimum Connectivity Inference Problem
Muhammad Abid Dar, Andreas Fischer, John Martinovic, Guntram Scheithauer
Minimum Diameter ColorSpanning Sets Revisited
Jonas Pruente
The Stable Set Problem: Clique and Nodal Inequalities Revisited
Adam N. Letchford, Fabrizio Rossi, Stefano Smriglio
Approximation Algorithms
A new approximation algorithm for unrelated parallel machine scheduling problem with release dates
Zhi Pei, Mingzhong Wan, Ziteng Wang
Optimal switching sequence for switched linear systems
Zeyang Wu, Qie He
Polyhedra
Extended Formulations for Radial Cones
Matthias Walter, Stefan Weltge
June 2018
Approximation Algorithms
An Approximation Algorithm for Vehicle Routing with Compatibility Constraints
Miao Yu, Viswanath Nagarajan, Siqian Shen
Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems
Jeanfrançois Cordeau, Fabio Furini, Ivana Ljubic
Polyhedra
New facets for the consecutive ones polytope
Luigi De Giovanni, Laura Brentegani, Mattia Festa
July 2018
The sharpest column: stabilizing column generation for the bin packing problem via a lexicographic pricer
Stefano Coniglio, Fabio D’Andreagiovanni, Fabio Furini
Why is maximum clique often easy in practice?
Jose L. Walteros, Buchanan Austin
On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem
Yotaro Takazawa, Shinji Mizuno
Branch and Cut Algorithms
Best case exponential running time of a branchandbound algorithm using an optimal semidefinite relaxation
Florian Jarre
August 2018
Efficient heuristic algorithm for identifying critical nodes in planar networks
Dalaijargal Purevusren, Gang Cui
On Lifted Cover Inequalities: A New Lifting Procedure with Unusual Properties
Adam N. Letchford, Georgia Souli
September 2018
Greedy Systems of Linear Inequalities and Lexicographically Optimal Solutions
Satoru Fujishige
October 2018
Mathematical models for stable matching problems with ties and incomplete lists
Maxence Delorme, Sergio García, Jacek Gondzio, Joerg Kalcsics, David Manlove, William Pettersson
Approximation Algorithms
An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks
Evren Güney
November 2018
Other
On the use of the simplex method for a type of allocation problems
Yoshihiro Tanaka
A fast exact algorithm for discrete resource allocation with nested constraints
Zeyang Wu, Qie He, Kameng Nip
A Tutorial on Formulating QUBO Models
Fred Glover, Gary Kochenberger
December 2018
On prime and minimal representations of a face of a polyhedron
Ta Van Tu
An improved analysis for algorithms on cuts and scheduling
Simai He, Suyuan Luo, Haoyue Wang
Branch and Cut Algorithms
A New Extended Formulation with Valid Inequalities for the Capacitated Concentrator Location Problem
Massimo Di Francesco, Manlio Gaudioso, Enrico Gorgone, Ishwar Murthy
Approximation Algorithms
A faster FPTAS for counting tworowed contingency tables
Tzvi Alon, Nir Halman
