Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties

No abstract is available for this paper.

• Publication year

  2014

• Venue

  Algorithmica

• Publication date

  2014-07-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-014-9911-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter

  2013cited by this paper
• A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties

  2013cited by this paper
• Approximation Algorithms for Integrated Distribution Network Design Problems

  2013cited by this paper
• Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty

  2013cited by this paper
• A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

  2011cited by this paper
• A 1.488 approximation algorithm for the uncapacitated facility location problem

  2011influential reference
• Approximation algorithms for supply chain planning and logistics problems with market choice

  2011influential reference
• An approximation algorithm for the k-level capacitated facility location problem

  2010cited by this paper
• Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design

  2009cited by this paper
• Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization

  2007cited by this paper
• An Approximation Algorithm for the Dynamic Facility Location Problem

  2006cited by this paper
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs

  2006cited by this paper
• Approximation Algorithms for Metric Facility Location Problems

  2006cited by this paper
• A new approximation algorithm for the k-facility location problem

  2006cited by this paper
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

  2006cited by this paper
• Network design for information networks

  2005cited by this paper
• Approximation Algorithms for Facility Location Problems ( Lecture Notes )

  2005cited by this paper
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem

  2005cited by this paper
• An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

  2005cited by this paper
• An improved approximation algorithm for uncapacitated facility location problem with penalties

  2005cited by this paper
• Stochastic Transportation-Inventory Network Design Problem

  2005cited by this paper
• Approximating the two-level facility location problem via a quasi-greedy approach

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

  2004cited by this paper
• Facility location and the analysis of algorithms through factor-revealing programs

  2004cited by this paper
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem

  2003cited by this paper
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem

  2003cited by this paper
• A new greedy approach for facility location problems

  2002influential reference
• Improved Approximation Algorithms for Metric Facility Location Problems

  2002cited by this paper
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP

  2002influential reference
• An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

  2002cited by this paper
• Algorithms for facility location problems with outliers

  2001cited by this paper
• Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

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

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

  2000cited by this paper
• Improved combinatorial algorithms for the facility location and k-median problems

  1999cited by this paper
• A 3-Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem

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

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

  1997cited by this paper
• Submodular functions and optimization

  1991cited by this paper

• Approximation algorithm for k-Product uncapacitated facility location problem with submodular penalties

  2026cites this paper
• A Survey of Approximation Algorithms for the Universal Facility Location Problem

  2025influential citation
• Uniform capacitated facility location with outliers/penalties

  2025cites this paper
• Approximation algorithms for the fault-tolerant facility location problem with submodular penalties

  2024cites this paper
• Randomized Rounding Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

  2024cites this paper
• An approximation algorithm for the -prize-collecting multicut problem in trees with submodular penalties

  2024cites this paper
• The facility location problem with maximum distance constraint

  2023cites this paper
• A combinatorial approximation algorithm for k-level facility location problem with submodular penalties

  2023cites this paper
• k-prize-collecting minimum

  2022cites this paper
• A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties

  2022cites this paper
• A note on LP-based approximation algorithms for capacitated facility location problem

  2022cites this paper
• Local search yields a PTAS for fixed-dimensional k-means problem with penalties

  2022cites this paper
• Locating Charging Stations: Connected, Capacitated and Prize- Collecting

  2022cites this paper
• Efficient Allocation for Downlink Multi-Channel NOMA Systems Considering Complex Constraints

  2021cites this paper
• Single Machine Vector Scheduling with General Penalties

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

  2021influential citation
• An approximation algorithm for the k-level facility location problem with outliers

  2021cites this paper
• Approximation algorithms for the multiprocessor scheduling with submodular penalties

  2021cites this paper
• An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

  2021cites this paper
• Local search algorithm for the squared metric $ k $-facility location problem with linear penalties

  2021cites this paper
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems

  2020cites this paper
• Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty

  2020cites this paper
• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

  2020cites this paper
• An LP-Rounding Based Algorithm for a Uniform Capacitated Facility Location Problem with Penalties

  2020cites this paper
• Approximating the τ-relaxed soft capacitated facility location problem

  2020cites this paper
• An approximation algorithm for submodular hitting set problem with linear penalties

  2020cites this paper
• Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties

  2020cites this paper
• Uniform Capacitated Facility Location Problems with Penalties/Outliers

  2020cites this paper
• Fractional 0–1 programming and submodularity

  2020cites this paper
• Uniform Capacitated Facility Location Problems with Penalties/Outliers

  2020cites this paper
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

  2020cites this paper
• A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties

  2019cites this paper
• Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection

  2019cites this paper
• Concave connection cost Facility Location and the Star Inventory Routing problem

  2019influential citation
• An Improved Approximation Algorithm for the k-Means Problem with Penalties

  2019cites this paper
• Approximation algorithms for the fault-tolerant facility location problem with penalties

  2019cites this paper
• Local search approximation algorithms for the k-means problem with penalties

  2018cites this paper
• An approximation algorithm for the k-median problem with uniform penalties via pseudo-solution

  2018cites this paper
• Scheduling for Time-Constrained Big-File Transfer Over Multiple Paths in Cloud Computing

  2018cites this paper
• Fast submodular maximization subject to k-extendible system constraints

  2018cites this paper
• An O(log1.5n log log n) Approximation Algorithm for Mean Isoperimetry and Robust k-means

  2018cites this paper
• Approximation algorithms for the robust facility leasing problem

  2018influential citation
• Scheduling algorithms for time-constrained big-file transfers in the Internet of Vehicles

  2017cites this paper
• Distribution optimization of the specialized car repair store based on the maximization of market share

  2017cites this paper
• A Local Search Approximation Algorithm for the k-means Problem with Penalties

  2017cites this paper
• Improved approximation algorithm for universal facility location problem with linear penalties

  2017cites this paper
• A note on the submodular vertex cover problem with submodular penalties

  2017cites this paper
• On the Factor Revealing LP Approach for Facility Location with Penalties

  2016influential citation
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique

  2016cites this paper
• An approximation algorithm for k-facility location problem with linear penalties using local search scheme

  2016cites this paper
• Facility Leasing with Penalties

  2016cites this paper
• An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions

  2016cites this paper
• An approximation algorithm for the nth power metric facility location problem with linear penalties

  2015influential citation
• Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties

  2015cites this paper
• Approximation Algorithms for the Multilevel Facility Location Problem with Linear/Submodular Penalties

  2015cites this paper
• A (5.83 + ϵ)-Approximation Algorithm for Universal Facility Location Problem with Linear Penalties

  2015cites this paper
• Local search algorithm for universal facility location problem with linear penalties

  2015cites this paper
• Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

  2014influential citation
• Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter

  2013cites this paper
• LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties

  year unknowncites this paper