Dynamic node packing
From MaRDI portal
Publication:2097666
DOI10.1007/s10107-021-01624-3zbMath1506.90229OpenAlexW3131677305MaRDI QIDQ2097666
Christopher Muir, Alejandro Toriello
Publication date: 14 November 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-01624-3
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Markov and semi-Markov decision processes (90C40)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximizing a class of submodular utility functions
- The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- On maximal independent sets of vertices in claw-free graphs
- A class of facet producing graphs for vertex packing polyhedra
- Geometric algorithms and combinatorial optimization.
- The maximum clique problem
- Wheel inequalities for stable set polytopes
- The relation of time indexed formulations of single machine scheduling problems to the node packing problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Routing trains through a railway station based on a node packing model
- Exact algorithms for maximum clique: a computational study
- A polyhedral approach to online bipartite matching
- Online independent sets.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Speeding up branch and bound algorithms for solving the maximum clique problem
- A review of dynamic vehicle routing problems
- Advice complexity of maximum independent set in sparse and bipartite graphs
- A review on algorithms for maximum clique problems
- An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation
- Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes
- On Circulant Matrices
- A Dynamic Traveling Salesman Problem with Stochastic Arc Costs
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- The Linear Programming Approach to Approximate Dynamic Programming
- Stochastic Scheduling with Release Dates and Due Dates
- A Characterization of Waiting Time Performance Realizable by Single-Server Queues
- Vertex packings: Structural properties and algorithms
- A Renewal Decision Problem
- On the Shannon capacity of a graph
- Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Properties of vertex packing and independence system polyhedra
- Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems
- Reducibility among Combinatorial Problems
- Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
- On the facial structure of set packing polyhedra
- New facets for the set packing polytope
- Finding a maximal weighted independent set in wireless networks
