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