Smoothed performance guarantees for local search

DOI10.1007/s10107-013-0683-7zbMath1325.68310OpenAlexW2069442517MaRDI QIDQ403643

Tjark Vredeveld, Heiko Röglin, Tobias Brunsch, Cyriel Rutten

Publication date: 29 August 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-013-0683-7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Search theory (90B40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (3)

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Smoothed Analysis of Local Search Algorithms ⋮ Bounds for the Convergence Time of Local Search in Scheduling Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees of jump neighborhoods on restricted related parallel machines
• Theoretical aspects of local search.
• Scheduling unit-length jobs with machine eligibility restrictions
• Tradeoffs in worst-case equilibria
• Topology matters: smoothed competitiveness of metrical task systems
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Tight bounds for worst-case equilibria
• A linear time approximation algorithm for multiprocessor scheduling
• Scheduling parallel machines with inclusive processing set restrictions
• Smoothed analysis of algorithms
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Bounds for List Schedules on Uniform Processors
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Probability Inequalities for Sums of Bounded Random Variables
• Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
• Parallel machine scheduling with job assignment restrictions
• A Survey of Approximation Results for Local Search Algorithms
• Bounds for Certain Multiprocessing Anomalies
• Tradeoffs and Average-Case Equilibria in Selfish Routing
• Random knapsack in expected polynomial time

This page was built for publication: Smoothed performance guarantees for local search