A survey on combinatorial optimization in dynamic environments

DOI10.1051/RO/2011114zbMATH Open1254.90186OpenAlexW2030769978MaRDI QIDQ2907959FDOQ2907959

Authors: Nicolas Boria, Vangelis Th. Paschos 

Publication date: 4 September 2012

Published in: RAIRO. Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2011__45_3_241_0/

Recommendations

• Dynamic optimization problems: approaches and perspectives
• Complexity and approximation in reoptimization
• A theory and algorithms for combinatorial reoptimization
• Reoptimization of NP-Hard Problems
• A theory and algorithms for combinatorial reoptimization

zbMATH Keywords

graphcomplexityapproximationon-line algorithmsprobabilistic optimizationreoptimizationhereditary problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Graph minors. XX: Wagner's conjecture
• A 71/60 theorem for bin packing
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• A data structure for dynamic trees
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
• A new approach to dynamic all pairs shortest paths
• A Vehicle Routing Problem with Stochastic Demand
• A linear-time approximation algorithm for the weighted vertex cover problem
• Probabilistic a priori routing-location problems
• Traveling Salesman Facility Location Problems
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• The Traveling Salesman Problem with Distances One and Two
• Improved bounds for harmonic-based bin packing algorithms
• An improved lower bound for on-line bin packing algorithms
• Fast algorithms for bin packing
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• A \(\frac78\)-approximation algorithm for metric Max TSP
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Title not available (Why is that?)
• A Priori Optimization
• Algorithms for the on-line travelling salesman
• The probabilistic minimum spanning tree problem
• Sparsification—a technique for speeding up dynamic graph algorithms
• The Probabilistic Minimum Vertex-covering Problem
• On finding minimal length superstrings
• Reoptimization of the metric deadline TSP
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Online algorithms: a survey
• Online independent sets.
• Title not available (Why is that?)
• Complexity and approximation in reoptimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
• On the Hardness of Reoptimization
• A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts
• Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
• Simple and fast reoptimizations for the Steiner tree problem
• Title not available (Why is that?)
• Reoptimizing the traveling salesman problem
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimizing the 0-1 knapsack problem
• On finite affine line transitive planes
• Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
• Reoptimization of Steiner Trees
• The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract)
• Reoptimization of Weighted Graph and Covering Problems
• Reoptimization of maximum weight induced hereditary subgraph problems
• Title not available (Why is that?)
• Maintaining minimum spanning trees in dynamic graphs
• On-line maximum-order induced hereditary subgraph problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Scheduling with forbidden sets
• Reoptimization of Steiner trees: changing the terminal set
• Fast reoptimization for the minimum spanning tree problem
• The Steiner problem with edge lengths 1 and 2
• Non deterministic polynomial optimization problems and their approximations
• Mathematical Foundations of Computer Science 2005
• Reoptimization of the Shortest Common Superstring Problem
• On randomized online scheduling
• On the online track assignment problem
• On the value of a random minimum spanning tree problem
• On-line vertex-covering
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Reoptimization of minimum and maximum traveling salesman's tours
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Complexity models for incremental computation
• Incremental algorithms for minimal length paths
• Title not available (Why is that?)
• Sensitivity analysis for scheduling problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Shortest path problems with node failures
• The probabilistic longest path problem
• A priori optimization for the probabilistic maximum independent set problem
• Probabilistic graph-coloring in bipartite and split graphs
• The parametric problem of shortest distances
• Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree
• A fully dynamic approximation scheme for shortest paths in planar graphs
• The probabilistic minimum coloring problem (extended abstract)
• Title not available (Why is that?)
• Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
• Probabilistic Combinatorial Optimization on Graphs
• On the probabilistic min spanning tree problem
• Title not available (Why is that?)
• Improved Data Structures for Fully Dynamic Biconnectivity

Cited In (10)

• Robust online algorithms for dynamic choosing problems
• Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices
• Title not available (Why is that?)
• New algorithms for Steiner tree reoptimization
• Evolutionary and population-based methods versus constructive search strategies in dynamic combinatorial optimization
• Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
• A note on the traveling salesman reoptimization problem under vertex insertion
• Reoptimization in machine scheduling
• Robust reoptimization of Steiner trees
• Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications

This page was built for publication: A survey on combinatorial optimization in dynamic environments

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