Worst-case analysis of clique MIPs
DOI10.1007/s10107-021-01706-2zbMath1504.90131OpenAlexW3201823262MaRDI QIDQ2089781
Jose L. Walteros, Mohammad Javad Naderi, Austin Buchanan
Publication date: 24 October 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01706-2
branch-and-bounddegeneracycliqueinteger programfixed-parameter tractability\(k\)-coreclique-core gap
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
- Exact exponential algorithms.
- Improved upper bounds for vertex cover
- Extended formulation for CSP that is compact for instances of bounded treewidth
- A simplification for some disjunctive formulations
- On the convex hull of the union of certain polyhedra
- Expressing combinatorial optimization problems by linear programs
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Facets for node packing
- Disjunctive programming: Properties of the convex hull of feasible points
- A multi-KP modeling for the maximum-clique problem
- The sandwich theorem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Extended formulations for vertex cover
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Parameterized top-\(K\) algorithms
- Conflict graphs in solving integer programming problems
- Preprocessing and cutting planes with conflict graphs
- On clique relaxation models in network analysis
- Balas formulation for the union of polytopes is optimal
- Tree-width and the Sherali-Adams operator
- Representation for multiple right-hand sides
- Extended and discretized formulations for the maximum clique problem
- The stable set problem: clique and nodal inequalities revisited
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Mixed Integer Linear Programming Formulation Techniques
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- An Analysis of Network Location Problems with Distance Constraints
- Modelling with integer variables
- The Cutting-Plane Method for Solving Convex Programs
- An Automatic Method of Solving Discrete Programming Problems
- Presolve Reductions in Mixed Integer Programming
- Parallel Maximum Clique Algorithms with Applications to Network Analysis
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Degree-two Inequalities, Clique Facets, and Biperfect Graphs
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Smallest-last ordering and clustering and graph coloring algorithms
- Vertex packings: Structural properties and algorithms
- On the Shannon capacity of a graph
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Extension Complexity of Independent Set Polytopes
- Properties of vertex packing and independence system polyhedra
- A tutorial on branch and cut algorithms for the maximum stable set problem
- Reducibility among Combinatorial Problems
- Why Is Maximum Clique Often Easy in Practice?
- On the facial structure of set packing polyhedra
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Contraction and Treewidth Lower Bounds
- An information complexity approach to extended formulations
- Parameterized Algorithms
- k-Degenerate Graphs
- The complexity of theorem-proving procedures
- On cliques in graphs
This page was built for publication: Worst-case analysis of clique MIPs
