Approximating incremental combinatorial optimization problems

DOI10.4230/LIPICS.APPROX-RANDOM.2017.6MaRDI QIDQ5002607zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, Francisco Unda

Publication date 28 July 2021

Full work available at URL https://dblp.uni-trier.de/db/conf/approx/approx2017.html#GoemansU17

zbMATH Keywords

approximation algorithmincremental problemsintegral polytopesmatchingmatroid intersectionstable sets

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An Incremental Model for Combinatorial Maximization Problems
• General bounds for incremental maximization
• scientific article; zbMATH DE number 2119736
• (1 + )-approximate incremental matching in constant deterministic amortized time
• Incremental network optimization: theory and algorithms

Cites work

• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Incremental network design with maximum flows
• Incremental network design with minimum spanning trees
• Incremental network design with shortest paths
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• Maximum matching and a polyhedron with 0,1-vertices
• On certain polytopes associated with graphs
• On maximal independent sets of vertices in claw-free graphs
• Paths, Trees, and Flowers

Cited in

(8)

• General bounds for incremental maximization
• General bounds for incremental maximization
• An Incremental Model for Combinatorial Maximization Problems
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• Optimal schemes for combinatorial query problems with integer feedback
• Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
• Incremental-decremental maximization
• Note on polynomial-time approximation schemes for integrated network design and scheduling problems

This page was built for publication: Approximating incremental combinatorial optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002607)