A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract)

DOI10.1007/978-3-319-48749-6_30zbMath1483.90074DBLPconf/cocoa/DingQ16OpenAlexW2539513543WikidataQ62043094 ScholiaQ62043094MaRDI QIDQ2958334

Wei Ding, Ke Qiu

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_30

zbMATH Keywords

treeedge-splittingquadratic timecontinuous connected 2-facility location

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Continuous location (90B85) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A linear time algorithm for computing a most reliable source on a tree network with faulty nodes
• Approximation algorithms for connected facility location problems
• Primal-dual algorithms for connected facility location problems
• Connected facility location via random facility sampling and core detouring
• Dual-Based Local Search for the Connected Facility Location and Related Problems
• Proof verification and the hardness of approximation problems
• Approximation Algorithms for Problems Combining Facility Location and Network Design
• Simpler and better approximation algorithms for network design
• Provisioning a virtual private network
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• A Branch and Cut Algorithm for a Steiner Tree-Star Problem

This page was built for publication: A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract)