Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}

DOI10.1016/j.dam.2023.11.021zbMath1530.05178arXiv1902.01874OpenAlexW2914313343MaRDI QIDQ6145803

Tom Denat, Nikolaos Melissinos, Ararat Harutyunyan, Vangelis Th. Paschos

Publication date: 9 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.01874

zbMATH Keywords

combinatorial optimizationapproximation schemeknapsack problemssubset-sums ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• Exact algorithms for maximum independent set
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• On the integrality gap of binary integer programs with Gaussian data
• Branch-and-bound solves random binary IPs in poly\((n)\)-time

This page was built for publication: Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}