Worst-case analysis of clique MIPs
type: Item
instance of: scholarly article
title: Worst-case analysis of clique MIPs
zbMATH Open document ID: 1504.90131
author: Mohammad Javad Naderi
author: Austin Buchanan
author: Jose L. Walteros
published in: Mathematical Programming. Series A. Series B
publication date: 2022-10-24T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7606024
zbMATH Keywords: integer program
zbMATH Keywords: branch-and-bound
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: clique
zbMATH Keywords: \(k\)-core
zbMATH Keywords: degeneracy
zbMATH Keywords: clique-core gap
describes a project that uses: Gurobi
describes a project that uses: MIPLIB
describes a project that uses: KaFFPa
describes a project that uses: SNAP
describes a project that uses: DIMACS
MaRDI profile type: Publication
full work available at URL: s10107-021-01706-2
OpenAlex ID: W3201823262
cites work: Presolve Reductions in Mixed Integer Programming
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Conflict graphs in solving integer programming problems
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: On the convex hull of the union of certain polyhedra
cites work: Disjunctive programming: Properties of the convex hull of feasible points
cites work: Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
cites work: Tree-width and the Sherali-Adams operator
cites work: Representation for multiple right-hand sides
cites work: Contraction and Treewidth Lower Bounds
cites work: Q3145799
cites work: Approximation Limits of Linear Programs (Beyond Hierarchies)
cites work: An information complexity approach to extended formulations
cites work: Preprocessing and cutting planes with conflict graphs
cites work: Extended formulations for vertex cover
cites work: Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
cites work: Parameterized top-\(K\) algorithms
cites work: Improved upper bounds for vertex cover
cites work: Balas formulation for the union of polytopes is optimal
cites work: The complexity of theorem-proving procedures
cites work: Q3651735
cites work: Parameterized Algorithms
cites work: A multi-KP modeling for the maximum-clique problem
cites work: Listing All Maximal Cliques in Large Sparse Real-World Graphs
cites work: Exponential lower bounds for polytopes in combinatorial optimization
cites work: Exact exponential algorithms.
cites work: Extension Complexity of Independent Set Polytopes
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: A simplification for some disjunctive formulations
cites work: Modelling with integer variables
cites work: Degree-two Inequalities, Clique Facets, and Biperfect Graphs
cites work: Reducibility among Combinatorial Problems
cites work: The Cutting-Plane Method for Solving Convex Programs
cites work: The sandwich theorem
cites work: Extended formulation for CSP that is compact for instances of bounded treewidth
cites work: An Automatic Method of Solving Discrete Programming Problems
cites work: Q3601990
cites work: The stable set problem: clique and nodal inequalities revisited
cites work: k-Degenerate Graphs
cites work: On the Shannon capacity of a graph
cites work: Extended and discretized formulations for the maximum clique problem
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: An Analysis of Network Location Problems with Distance Constraints
cites work: On cliques in graphs
cites work: Facets for node packing
cites work: Properties of vertex packing and independence system polyhedra
cites work: Vertex packings: Structural properties and algorithms
cites work: On the facial structure of set packing polyhedra

Worst-case analysis of clique MIPs (cites work)
cites work: On clique relaxation models in network analysis

Worst-case analysis of clique MIPs (cites work)
cites work: A tutorial on branch and cut algorithms for the maximum stable set problem

Worst-case analysis of clique MIPs (cites work)
cites work: Parallel Maximum Clique Algorithms with Applications to Network Analysis

Worst-case analysis of clique MIPs (cites work)
cites work: Preprocessing and Probing Techniques for Mixed Integer Programming Problems

Worst-case analysis of clique MIPs (cites work)
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)

Worst-case analysis of clique MIPs (cites work)
cites work: Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks

Worst-case analysis of clique MIPs (cites work)
cites work: Mixed integer linear programming formulation techniques

Worst-case analysis of clique MIPs (cites work)
cites work: Why Is Maximum Clique Often Easy in Practice?

Worst-case analysis of clique MIPs (cites work)
cites work: Expressing combinatorial optimization problems by linear programs

Worst-case analysis of clique MIPs (cites work)
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number

Worst-case analysis of clique MIPs (DOI)
DOI: 10.1007/S10107-021-01706-2

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: Computing and Combinatorics
Similarity Score: 0.8864214
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: The worst-case time complexity for generating all maximal cliques and computational experiments
Similarity Score: 0.8794215
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: On the approximability of clique and related maximization problems
Similarity Score: 0.86924726
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: Clustered maximum weight clique problem: algorithms and empirical analysis
Similarity Score: 0.866272
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: Exact algorithms for maximum clique: a computational study
Similarity Score: 0.86588943
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: On comparing algorithms for the maximum clique problem
Similarity Score: 0.8616619
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: CliSAT: a new exact algorithm for hard maximum clique problems
Similarity Score: 0.8589673
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
Similarity Score: 0.8587273
Recommender Run: Recommender Run 3

Worst-case analysis of clique MIPs (Recommended article)
Recommended article: ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
Similarity Score: 0.856086
Recommender Run: Recommender Run 3