Primal-dual approximation algorithms for metric facility location and k-median problems

No abstract is available for this paper.

• Publication year

  1999

• Venue

  40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)

• Publication date

  1999-10-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFFCS.1999.814571
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A primal-dual schema based approximation algorithm for the element connectivity problem

  2002cited by this paper
• Analysis of a local search heuristic for facility location problems

  2000cited by this paper
• The Capacitated K-Center Problem

  2000cited by this paper
• Approximation algorithms for facility location problems

  2000cited by this paper
• On the bidirected cut relaxation for the metric Steiner tree problem

  1999influential reference
• Improved approximation algorithms for capacitated facility location problems

  1999cited by this paper
• Óò×øøòø¹¹¹ Blockinøóö Ôôöóüüññøøóò Ððóööøøñ Óö Øøø ¹ñññññò Ôöóóððñ´´üøøòòòò ×øöö Blockinøµ

  1999cited by this paper
• Improved approximation algorithms for a capacitated facility location problem

  1999cited by this paper
• Mathematical Programming for Data Mining: Formulations and Challenges

  1999cited by this paper
• Rounding via Trees : Deterministic Approximation Algorithms forGroup

  1998cited by this paper
• Greedy strikes back: improved facility location algorithms

  1998cited by this paper
• Approximation schemes for Euclidean k-medians and related problems

  1998cited by this paper
• Improved Approximation Algorithms for Uncapacitated Facility Location

  1998cited by this paper
• An approximation algorithm for minimum-cost vertex-connectivity problems

  1997cited by this paper
• Approximation algorithms for facility location problems (extended abstract)

  1997cited by this paper
• Probabilistic approximation of metric spaces and its algorithmic applications

  1996cited by this paper
• The Capacitated K-Center Problem (Extended Abstract)

  1996cited by this paper
• Improved approximation algorithms for network design problems

  1994influential reference
• Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover

  1993cited by this paper
• How to Allocate Network Centers

  1993cited by this paper
• A primal-dual approximation algorithm for generalized steiner network problems

  1993influential reference
• Approximations with Minimum Packing Constraint Violation

  1992cited by this paper
• e-approximations with minimum packing constraint violation (extended abstract)

  1992cited by this paper
• A general approximation technique for constrained forest problems

  1992influential reference
• Approximation Algorithms for Geometric Median Problems

  1992cited by this paper
• When trees collide: an approximation algorithm for the generalized Steiner problem on networks

  1991cited by this paper
• Discrete Location Theory

  1991cited by this paper
• Discrete location theory

  1991cited by this paper
• A personal communication

  1989cited by this paper
• Heuristics for the fixed cost median problem

  1982cited by this paper
• A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem

  1981cited by this paper
• A Plant and Warehouse Location Problem

  1977cited by this paper
• Maximum matching and a polyhedron with 0,1-vertices

  1965cited by this paper
• A Working Model for Plant Numbers and Locations

  1963cited by this paper
• A Heuristic Program for Locating Warehouses

  1963cited by this paper

• On Tight FPT Time Approximation Algorithms for k-Clustering Problems

  2025cites this paper
• Improved lower bound for differentially private facility location

  2025cites this paper
• Malware Containment Via Firewall Placement in Iot Networks

  2025cites this paper
• Optimal Interactive Learning on the Job via Facility Location Planning

  2025cites this paper
• Battery Swapping Tour Optimization Problem in Dockless Electric Bike Sharing Service Systems With Distance-Aware User Incentives

  2025cites this paper
• Facility Location and k-Median with Fair Outliers

  2025cites this paper
• Facility location and restoration games

  2024cites this paper
• Deploying Wireless-Powered UAV Base Stations for Maximizing Throughput

  2024cites this paper
• A Scalable Solution for the Extended Multi-channel Facility Location Problem

  2023cites this paper
• Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties

  2023cites this paper
• Clustering Graphs of Bounded Treewidth to Minimize the Sum of Radius-Dependent Costs

  2023cites this paper
• Approximate Group Fairness for Clustering

  2022cites this paper
• Provable randomized rounding for minimum-similarity diversification

  2022cites this paper
• An improved primal-dual approximation algorithm for the k-means problem with penalties

  2021cites this paper
• Optimizing strategies for post-disaster reconstruction of school systems

  2021cites this paper
• A Cost-Sharing Scheme for the k-Level Facility Location Game with Penalties

  2021cites this paper
• Approximation Algorithms for Clustering with Dynamic Points

  2020cites this paper
• An improved (1+1) evolutionary algorithm for k-median clustering problem with performance guarantee

  2020cites this paper
• Proportionally Fair Clustering

  2019influential citation
• Towards robust controller placement in software-defined networks against links failure

  2019influential citation
• On Distributed Algorithms for Cost-Efficient Data Center Placement in Cloud Computing

  2018cites this paper
• Improved Approximation Algorithms for Facility Location Problems

  2018influential citation
• A Source Coding Perspective on Node Deployment in Two-Tier Networks

  2018cites this paper
• A Benders Decomposition Approach for Resilient Placement of Virtual Process Control Functions in Mobile Edge Clouds

  2018cites this paper
• On Minimizing Supermodular Functions on Hereditary Systems

  2018cites this paper
• Coresets for $k$-Means and $k$-Median Clustering and their Applications

  2018cites this paper
• Solving Optimization Problems via Maximum Satisfiability: Encodings and Re-Encodings

  2018cites this paper
• Title A Source Coding Perspective on Node Deployment in Two-Tier Networks Permalink

  2018cites this paper
• Distributed Vehicle Routing Approximation

  2017cites this paper
• ORSCA: Optimal Route Selection and Communication Association for Drones in WSNs

  2017cites this paper
• Clustering through Continuous Facility Location Problems

  2017cites this paper
• Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic

  2017cites this paper
• Solving Capacitated Data Storage Placement Problems in Sensor Networks

  2017influential citation
• 43 NEAREST NEIGHBORS IN HIGH-DIMENSIONAL SPACES

  2017cites this paper
• Number : WUCSE-2002-5 2002-0131 Placing Servers in Overlay Networks

  2016cites this paper
• Clustering Problems on Sliding Windows

  2016cites this paper
• Approximate solution of the p-median minimization problem

  2016cites this paper
• Aggregation points planning for software-defined network based smart grid communications

  2016cites this paper
• Semimetric Properties of Sørensen-Dice and Tversky Indexes

  2016cites this paper
• Growing the charging station network for electric vehicles with trajectory data analytics

  2015cites this paper
• Metric k-median Problem and Its Application in Reverse Greedy RandomizedAlgorithm

  2015cites this paper
• Adaptive Grid-Based k-median Clustering of Streaming Data with Accuracy Guarantee

  2015cites this paper
• Semantically Formalized Logging and Advanced Analytics for Enhanced Monitoring and Management of Large-scale Applications

  2015cites this paper
• A Unified Approach for Clustering Problems on Sliding Windows

  2015cites this paper
• Aggregation Points Planning in Smart Grid Communication System

  2015cites this paper
• Elastic virtual machine placement in cloud computing network environments

  2015cites this paper
• Applications of Biased Randomization and Simheuristic Algorithms to Arc Routing and Facility Location Problems

  2015influential citation
• A novel approach to solve K-center problems with geographical placement

  2015cites this paper
• Approximation algorithms for resource allocation optimization.

  2014influential citation
• Distributed Server Migration for Scalable Internet Service Deployment

  2014cites this paper
• An optimal solution for the Uncapacitated Facility Location Problem using the dual formulation

  2014cites this paper
• Service allocation methodologies for contributory computing environments

  2014cites this paper
• Dynamic Content Delivery Infrastructure Deployment using Network Cloud Resources

  2014cites this paper
• Fault-Tolerant Facility Allocation

  2013cites this paper
• Distributed Approximation Algorithms for Facility Location Problems

  2013cites this paper
• A Fast Algorithm for Facility Location Problem

  2013cites this paper
• Combinatorial Optimization Problems in Geometric Settings

  2013cites this paper
• Approximation Algorithms for Fault Tolerant Facility Allocation

  2013influential citation
• A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

  2013cites this paper
• Heuristic algorithms for general k-level facility location problems

  2013cites this paper
• Optimisation d'un réseau de distribution de contenus géré par un opérateur réseauOptimization of vido Delivery in Telco-CDN

  2013cites this paper
• New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem

  2012influential citation
• Online Problems in Facility Location

  2012cites this paper
• A cost-sharing method for an uncapacitated facility location game with penalties

  2012cites this paper
• Some Distributed Approaches to the Service Facility Location Problem inDynamic and Complex Networks

  2012cites this paper
• Scalable facility placement for communication cost reduction in wireless networks

  2012cites this paper
• Approximation algorithms for clustering problems

  2012cites this paper
• Probabilistic k-Median Clustering in Data Streams

  2012cites this paper
• Polynomial Time Approximation S hemes for Metri Min-Sum Clustering

  2011cites this paper
• Algorithms for Constructing Overlay Networks For Live Streaming

  2011cites this paper
• Research on randomized greedy algorithm for k-median problem

  2011influential citation
• Selfish Overlay Network Creation and Maintenance

  2011cites this paper
• Optimal network locality in distributed virtualized data-centers

  2011cites this paper
• A Comparison of Clustering Algorithms for Data Streams

  2011cites this paper
• Multi-facility ordered median problems in directed networks

  2011cites this paper
• Distributed Server Migration for Scalable Internet Service Deployment

  2011influential citation
• Squared Metric Facility Location Problem

  2011cites this paper
• Degree-Based Spanning Tree Optimization

  2010cites this paper
• Faster Facility Location and Hierarchical Clustering

  2010cites this paper
• An approximation algorithm for the k-level capacitated facility location problem

  2010cites this paper
• Cache Me if You Can: Capacitated Selfish Replication Games in Networks

  2010cites this paper
• Capacitated Caching Games

  2010cites this paper
• Scalable service migration in autonomic network environments

  2010influential citation
• An algorithm for the facility location problems

  2010influential citation
• Accelerating the local search algorithm for the facility location

  2010influential citation
• Achieving anonymity via clustering

  2010cites this paper
• Algorithms for Manipulation with Large Geometric and Graphic Data

  2009cites this paper
• Approximation algorithm for k-level hard capacitated facility location problem

  2009cites this paper
• The Fault-Tolerant Facility Allocation Problem

  2009cites this paper
• Improving on-demand data access efficiency in MANETs with cooperative caching

  2009cites this paper
• Overlay network creation and maintenance with selfish users

  2009cites this paper
• Optimal-location queries over spatial databases

  2009cites this paper
• A Cost-Sharing Method for the Soft-Capacitated Economic Lot-Sizing Game

  2009cites this paper
• A cost-sharing method for an economic lot-sizing game

  2009cites this paper
• A density-based clustering over evolving heterogeneous data stream

  2009cites this paper
• Achieving Anonymity via Clustering

  2008influential citation
• Comparison and analysis of ten static heuristics-based Internet data replication techniques

  2008cites this paper
• A General k-Level Uncapacitated Facility Location Problem

  2008cites this paper
• Lotsize optimization leading to a p-median problem with cardinalities

  2008cites this paper
• Lecture 4: Uncapacitated Facility Location

  2008cites this paper