scientific article
From MaRDI portal
Publication:2768359
zbMath1012.90026MaRDI QIDQ2768359
Giri Narasimhan, Samir Khuller, David M. Mount, Moses Charikar
Publication date: 30 January 2002
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)
Related Items (only showing first 100 items - show all)
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ New approximation results for resource replication problems ⋮ Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ Exact algorithms for handling outliers in center location problems on networks using \(k\)-max functions ⋮ A Technique for Obtaining True Approximations for k-Center with Covering Constraints ⋮ Fair Colorful k-Center Clustering ⋮ An improved primal-dual approximation algorithm for the k-means problem with penalties ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ A cost-sharing scheme for the \(k\)-level facility location game with penalties ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Matroid and knapsack center problems ⋮ Asymmetric \(k\)-center with minimum coverage ⋮ An improved approximation algorithm for squared metric \(k\)-facility location ⋮ Online network design with outliers ⋮ Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties ⋮ A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties ⋮ A primal-dual approximation algorithm for partial vertex cover: Making educated guesses ⋮ Approximation algorithm for uniform bounded facility location problem ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Approximation algorithms for clustering with dynamic points ⋮ A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks ⋮ Approximation Algorithms for the Robust Facility Location Problem with Penalties ⋮ An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties ⋮ On some variants of Euclidean \(k\)-supplier ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Group parking permit problems ⋮ Discrete facility location in machine learning ⋮ An approximation algorithm for the dynamic facility location problem with submodular penalties ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ An approximation algorithm for the dynamic facility location problem with outliers ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ On the complexity of some problems of searching for a family of disjoint clusters ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ Improved approximation algorithm for universal facility location problem with linear penalties ⋮ Facility Location Problems: A Parameterized View ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On a class of subadditive duals for the uncapacitated facility location problem ⋮ A primal-dual approximation algorithm for the facility location problem with submodular penalties ⋮ Approximation algorithms for the priority facility location problem with penalties ⋮ A unified approach to approximating partial covering problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier ⋮ Approximation algorithms for supply chain planning and logistics problems with market choice ⋮ Mathematical programming models for determining the optimal location of beehives ⋮ Implicit branching and parameterized partial cover problems ⋮ Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach ⋮ Helly-Type Theorems in Property Testing ⋮ A cost-sharing method for an uncapacitated facility location game with penalties ⋮ Black-box reductions for cost-sharing mechanism design ⋮ A Lottery Model for Center-Type Problems with Outliers ⋮ Approximation Algorithm for the Uniform Bounded Facility Problem ⋮ Approximation Algorithm for Resource Allocation Problems with Time Dependent Penalties ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Local search algorithm for universal facility location problem with linear penalties ⋮ A streaming algorithm for 2-center with outliers in high dimensions ⋮ Parallel approximation for partial set cover ⋮ Approximation algorithms for the robust facility leasing problem ⋮ Approximation algorithms for the robust/soft-capacitated 2-level facility location problems ⋮ Local search algorithms for the red-blue median problem ⋮ An application of a Lagrangian-type relaxation for the uncapacitated facility location problem ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Unnamed Item ⋮ Min sum clustering with penalties ⋮ A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ Facility location problems: a parameterized view ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Asymmetry in \(k\)-center variants ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ Learning big (image) data via coresets for dictionaries ⋮ Local search algorithm for the spherical \(k\)-means problem with outliers ⋮ Improved approximation for prize-collecting red-blue median ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ Approximation algorithms for the partition vertex cover problem ⋮ An Approximation Algorithm for the k-Level Uncapacitated Facility Location Problem with Penalties ⋮ Improved approximation algorithms for the facility location problems with linear/submodular penalties ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ Generalized Center Problems with Outliers ⋮ On the power of static assignment policies for robust facility location problems ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ An improved approximation algorithm for uncapacitated facility location problem with penalties ⋮ An LP rounding algorithm for approximating uncapacitated facility location problem with penalties ⋮ Approximation algorithms for the covering-type \(k\)-violation linear program ⋮ The incremental connected facility location problem ⋮ An approximation algorithm for the spherical \(k\)-means problem with outliers by local search ⋮ Improved approximation algorithms for solving the squared metric \(k\)-facility location problem ⋮ Improved approximation algorithms for multilevel facility location problems ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties ⋮ Approximation and complexity of the capacitated geometric median problem ⋮ Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties) ⋮ Concave connection cost facility location and the star inventory routing problem ⋮ A technique for obtaining true approximations for \(k\)-center with covering constraints ⋮ Fair colorful \(k\)-center clustering
This page was built for publication:
