Title: Approximation Algorithms for Replenishment Problems with Fixed Turnover Times
Abstract
We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives:min–avg minimizes the average tour cost andmin–max minimizes the maximum tour cost over all days. Formin–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. Formin–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.
Becker, Amariah; Klein, Philip N; Schild, Aaron(
, Proceedings of the 16th International Symposium on Algorithms and Data Structures, WADS 2019)
null
(Ed.)
The Capacitated Vehicle Routing problem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot and is subject to a capacity bound on the number of clients it can serve. In this paper, we present a polynomial-time approximation scheme (PTAS) for instances in which the input graph is planar and the capacity is bounded. Previously, only a quasipolynomial-time approximation scheme was known for these instances. To obtain this result, we show how to embed planar graphs into bounded-treewidth graphs while preserving, in expectation, the client-to-client distances up to a small additive error proportional to client distances to the depot.
Garg, Naveen; Khanna, Sanjeev; Kumar, Amit(
, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms)
null
(Ed.)
Vehicle routing problems are a broad class of combinatorial optimization problems that can be formulated as the problem of finding a tour in a weighted graph that optimizes some function of the visited vertices. For instance, a canonical and extensively studied vehicle routing problem is the orienteering problem where the goal is to find a tour that maximizes the number of vertices visited by a given deadline. In this paper, we consider the computational tractability of a well-known generalization of the orienteering problem called the Orient-MTW problem. The input to Orient-MTW consists of a weighted graph G(V, E) where for each vertex v ∊ V we are given a set of time instants Tv ⊆ [T], and a source vertex s. A tour starting at s is said to visit a vertex v if it transits through v at any time in the set Tv. The goal is to find a tour starting at the source vertex that maximizes the number of vertices visited. It is known that this problem admits a quasi-polynomial time O(log OPT)-approximation ratio where OPT is the optimal solution value but until now no hardness better than an APX-hardness was known for this problem.
Our main result is an -hardness for this problem that holds even when the underlying graph G is an undirected tree. This is the first super-constant hardness result for the Orient-MTW problem. The starting point for our result is the hardness of the SetCover problem which is known to hold on instances with a special structure. We exploit this special structure of the hard SetCover instances to first obtain a new proof of the APX-hardness result for Orient-MTW that holds even on trees of depth 2. We then recursively amplify this constant factor hardness to an -hardness, while keeping the resulting topology to be a tree. Our amplified hardness proof crucially utilizes a delicate concavity property which shows that in our encoding of SetCover instances as instances of the Orient-MTW problem, whenever the optimal cost for SetCover instance is large, any tour, no matter how it allocates its time across different sub-trees, can not visit too many vertices overall. We believe that this reduction template may also prove useful in showing hardness of other vehicle routing problems.
Gupta, Swati; Moondra, Jai; Singh, Mohit(
, EC '23: Proceedings of the 24th ACM Conference on Economics and Computation)
Given a set of facilities and clients, and costs to open facilities, the classic facility location problem seeks to
open a set of facilities and assign each client to one open facility to minimize the cost of opening the chosen
facilities and the total distance of the clients to their assigned open facilities. Such an objective may induce an
unequal cost over certain socioeconomic groups of clients (i.e., total distance traveled by clients in such a
group). This is important when planning the location of socially relevant facilities such as emergency rooms.
In this work, we consider a fair version of the problem where we are given 𝑟 clients groups that partition
the set of clients, and the distance of a given group is defined as the average distance of clients in the group
to their respective open facilities. The objective is to minimize the Minkowski 𝑝-norm of vector of group
distances, to penalize high access costs to open facilities across 𝑟 groups of clients. This generalizes classic
facility location (𝑝 = 1) and the minimization of the maximum group distance (𝑝 = ∞). However, in practice,
fairness criteria may not be explicit or even known to a decision maker, and it is often unclear how to select a
specific "𝑝" to model the cost of unfairness. To get around this, we study the notion of solution portfolios where
for a fixed problem instance, we seek a small portfolio of solutions such that for any Minkowski norm 𝑝, one
of these solutions is an 𝑂(1)-approximation. Using the geometric relationship between various 𝑝-norms, we
show the existence of a portfolio of cardinality 𝑂(log 𝑟), and a lower bound of (\sqrt{log r}).
There may not be common structure across different solutions in this portfolio, which can make planning
difficult if the notion of fairness changes over time or if the budget to open facilities is disbursed over time. For
example, small changes in 𝑝 could lead to a completely different set of open facilities in the portfolio. Inspired
by this, we introduce the notion of refinement, which is a family of solutions for each 𝑝-norm satisfying a
combinatorial property. This property requires that (1) the set of facilities open for a higher 𝑝-norm must be
a subset of the facilities open for a lower 𝑝-norm, and (2) all clients assigned to an open facility for a lower
𝑝-norm must be assigned to the same open facility for any higher 𝑝-norm. A refinement is 𝛼-approximate if
the solution for each 𝑝-norm problem is an 𝛼-approximation for it. We show that it is sufficient to consider
only 𝑂(log 𝑟) norms instead of all 𝑝-norms, 𝑝 ∈ [1, ∞] to construct refinements. A natural greedy algorithm
for the problem gives a poly(𝑟)-approximate refinement, which we improve to poly(r^1/\sqrt{log 𝑟})-approximate
using a recursive algorithm. We improve this ratio to 𝑂(log 𝑟) for the special case of tree metric for uniform
facility open cost. Our recursive algorithm extends to other settings, including to a hierarchical facility location
problem that models facility location problems at several levels, such as public works departments and schools.
A full version of this paper can be found at https://arxiv.org/abs/2211.14873.
Bruce Maggs, Arun Ganesh(
, Leibniz international proceedings in informatics)
Bansal, Nikhil and
(Ed.)
his paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution.
Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.
We study a general stochastic ranking problem in which an algorithm needs to adaptively select a sequence of elements so as to “cover” a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, in which the scenario is said to be covered when its function value goes above a given threshold. We obtain a logarithmic factor approximation algorithm for this adaptive ranking problem, which is the best possible (unless P = NP). This problem unifies and generalizes many previously studied problems with applications in search ranking and active learning. The approximation ratio of our algorithm either matches or improves the best result known in each of these special cases. Furthermore, we extend our results to an adaptive vehicle-routing problem, in which costs are determined by an underlying metric. This routing problem is a significant generalization of the previously studied adaptive traveling salesman and traveling repairman problems. Our approximation ratio nearly matches the best bound known for these special cases. Finally, we present experimental results for some applications of adaptive ranking.
Bosman, Thomas, van Ee, Martijn, Jiao, Yang, Marchetti-Spaccamela, Alberto, Ravi, R., and Stougie, Leen.
"Approximation Algorithms for Replenishment Problems with Fixed Turnover Times". Algorithmica 84 (9). Country unknown/Code not available: Springer Science + Business Media. https://doi.org/10.1007/s00453-022-00974-4.https://par.nsf.gov/biblio/10369259.
@article{osti_10369259,
place = {Country unknown/Code not available},
title = {Approximation Algorithms for Replenishment Problems with Fixed Turnover Times},
url = {https://par.nsf.gov/biblio/10369259},
DOI = {10.1007/s00453-022-00974-4},
abstractNote = {Abstract We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives:min–avg minimizes the average tour cost andmin–max minimizes the maximum tour cost over all days. Formin–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. Formin–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.},
journal = {Algorithmica},
volume = {84},
number = {9},
publisher = {Springer Science + Business Media},
author = {Bosman, Thomas and van Ee, Martijn and Jiao, Yang and Marchetti-Spaccamela, Alberto and Ravi, R. and Stougie, Leen},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.
