A survey on combinatorial optimization in dynamic environments
From MaRDI portal
Publication:2907959
DOI10.1051/ro/2011114zbMath1254.90186OpenAlexW2030769978MaRDI QIDQ2907959
Vangelis Th. Paschos, Nicolas Boria
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/
complexitygraphapproximationon-line algorithmsprobabilistic optimizationreoptimizationhereditary problem
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items
Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions ⋮ Robust reoptimization of Steiner trees ⋮ Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications ⋮ Unnamed Item ⋮ Reoptimization in machine scheduling ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices ⋮ Evolutionary and population-based methods versus constructive search strategies in dynamic combinatorial optimization ⋮ Robust online algorithms for dynamic choosing problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Reoptimization of maximum weight induced hereditary subgraph problems
- On the online track assignment problem
- Reoptimizing the 0-1 knapsack problem
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Graph minors. XX: Wagner's conjecture
- Probabilistic graph-coloring in bipartite and split graphs
- Reoptimization of Steiner trees: changing the terminal set
- Fast reoptimization for the minimum spanning tree problem
- Reoptimization of minimum and maximum traveling salesman's tours
- On the value of a random minimum spanning tree problem
- A 71/60 theorem for bin packing
- On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
- The Steiner problem with edge lengths 1 and 2
- On finding minimal length superstrings
- Non deterministic polynomial optimization problems and their approximations
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- Improved bounds for harmonic-based bin packing algorithms
- An improved lower bound for on-line bin packing algorithms
- A characterization of linear admissible transformations for the m- travelling salesmen problem
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Complexity models for incremental computation
- A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts
- Online algorithms: a survey
- On-line vertex-covering
- A data structure for dynamic trees
- Fast algorithms for bin packing
- A \(\frac78\)-approximation algorithm for metric Max TSP
- Online independent sets.
- On the probabilistic min spanning tree problem
- Reoptimization of the metric deadline TSP
- On finite affine line transitive planes
- On the probabilistic minimum coloring and minimum \(k\)-coloring
- Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Probabilistic Combinatorial Optimization on Graphs
- The probabilistic minimum spanning tree problem
- Reoptimization of Steiner Trees
- The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality
- On randomized online scheduling
- Reoptimization of Weighted Graph and Covering Problems
- Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs
- Reoptimization of the Shortest Common Superstring Problem
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Incremental algorithms for minimal length paths
- Shortest path problems with node failures
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- P-Complete Approximation Problems
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
- The probabilistic longest path problem
- Probabilistic a priori routing-location problems
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- Sparsification—a technique for speeding up dynamic graph algorithms
- Reoptimizing the traveling salesman problem
- Improved Data Structures for Fully Dynamic Biconnectivity
- The Probabilistic Minimum Vertex-covering Problem
- Maintaining minimum spanning trees in dynamic graphs
- On-line maximum-order induced hereditary subgraph problems
- The Traveling Salesman Problem with Distances One and Two
- Analysis of Probabilistic Combinatorial Optimization Problems in Euclidean Spaces
- Traveling Salesman Facility Location Problems
- A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty
- Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
- \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- On the Hardness of Reoptimization
- Mathematical Foundations of Computer Science 2005
- The parametric problem of shortest distances
- Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree
- A Priori Optimization
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Graph-Theoretic Concepts in Computer Science
- Sensitivity analysis for scheduling problems
- Algorithms for the on-line travelling salesman
- A priori optimization for the probabilistic maximum independent set problem
- Scheduling with forbidden sets
- A Vehicle Routing Problem with Stochastic Demand
