Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two ...
详细信息
ISBN:
(纸本)9781450367059
Two-stage stochastic optimization is a widely used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise! To address this, an approach that is quite versatile and has gained popularity in the stochastic-optimization literature is the distributionally robust 2-stage model: given a collection D of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in D. We provide a framework for designing approximation algorithms in such settings when the collection D is a ball around a central distribution and the central distribution is accessed only via a sampling black box. We first show that one can utilize the sample average approximation (SAA) method-solve the distributionally robust problem with an empirical estimate of the central distribution-to reduce the problem to the case where the central distribution has polynomial-size support. Complementing this, we show how to approximately solve a fractional relaxation of the SAA (i.e., polynomial-scenario central-distribution) problem. Unlike in 2-stage stochastic- or robust-optimization, this turns out to be quite challenging. We utilize the ellipsoid method in conjunction with several new ideas to show that this problem can be approximately solved provided that we have an (approximation) algorithm for a certain max-min problem that is akin to, and generalizes, the k-maxmin problem-find the worst-case scenario consisting of at most k elements-encountered in 2-stage robust optimization. We
We consider vehicle-routing problems (VRPs) that incorporate the notion of regret of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we con...
详细信息
ISBN:
(纸本)9781450327107
We consider vehicle-routing problems (VRPs) that incorporate the notion of regret of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the regret-bounded vehicle routing problem (RVRP). In these problems, we are given an undirected complete graph G = ({r} U V, E) on n nodes with a distinguished root (depot) node r, edge costs {c(uv)} that form a metric, and a regret bound R. Given a path P rooted at r and a node v is an element of P, let cp(v) be the distance from r to v along P. The goal is to find the fewest number of paths rooted at r that cover all the nodes so that for every node v covered by (say) path P: (i) its additive regret cp(v) c, with respect to P is at most R in additive-RVRP;or (ii) its multiplicative regret, c(P) (v)/c(rv) with respect to P is at most R in multiplicative-RVRP. Our main result is the first constant-factor approximation algorithm for additive-RVRP. This is a substantial improvement over the previous-best O(log m)-approximation. Additive- RVRP turns out be a rather central vehicle-routing problem, whose study reveals insights into a variety of other regret-related problems as well as the classical distance-constrained VRP (DVRP), enabling us to obtain guarantees for these various problems by leveraging our algorithm for additive- RVRP and the underlying techniques. We obtain approximation ratios of O (log(R/R-1)) for multiplicativeRVRP, and O(min{OPT, log D/log log D}) for DVRP with distance bound D via reductions to additive-RVRP;the latter improves upon the previous-best approximation for DVRP. A noteworthy aspect of our results is that they are obtained by devising rounding techniques for a natural configuration-style LP. This furthers our understanding of LP-relaxations for VRPs and enriches the toolkit of techniques that have been utilized for configuration LPs.
The edge dominating set problem is one of the fundamental covering problems in the field of combinatorial optimization. In this paper, we consider the b-edge dominating set problem, a generalized version of the edge d...
详细信息
ISBN:
(纸本)3540280618
The edge dominating set problem is one of the fundamental covering problems in the field of combinatorial optimization. In this paper, we consider the b-edge dominating set problem, a generalized version of the edge dominating set problem. In this version, we are given a simple undirected graph G = (V, E) and a demand vector is an element of Z(E)(+). A set F of edges in G is called a b-edge dominating set if each edge e is an element of E is adjacent to at least b(e) edges in F, where we allow F to contain multiple copies of edges in E. Given a cost vector W is an element of Q(+)(E), the problem asks to find a minimum cost of a b-edge dominating set. We first show that there is a 8/3-approximation algorithm for this problem. We then consider approximation algorithms for other related problems.
We introduce the successive Hitting Set model, where the set system is not given in advance but a set generator produces the sets that contain a specific element from the universe on demand. Despite incomplete knowled...
详细信息
ISBN:
(纸本)9783662489710;9783662489703
We introduce the successive Hitting Set model, where the set system is not given in advance but a set generator produces the sets that contain a specific element from the universe on demand. Despite incomplete knowledge about the set system, we show that several approximation algorithms for the conventional Hitting Set problem can be adopted to perform well in this model. We describe, and experimentally investigate, several scenarios where the new model is beneficial compared to the conventional one.
We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [1]. In min-max generalization problems, the input consists of data. items with wei...
详细信息
ISBN:
(纸本)9783642153686
We provide improved approximation algorithms for the min-max generalization problems considered by Du, Eppstein, Goodrich, and Lueker [1]. In min-max generalization problems, the input consists of data. items with weights and a lower bound w(1b), and the goal is to partition individual items into groups of weight at least w(1b), while minimizing the maximum weight of a group. The rules of legal partitioning are specific to a problem. Du et al. consider several problems in this vein: (I) partitioning a graph into connected subgraphs, (2) partitioning unstructured data into arbitrary classes and (3) partitioning a 2-dimensional array into non-overlapping contiguous rectangles (subarrays) that satisfy the above size requirements. We significantly improve approximation ratios for all the problems considered by Du et al., and provide additional motivation for these problems. Moreover, for the first problem, while Du et al. give approximation algorithms for specific graph families, namely, 3-connected and 4-connected planar graphs, no approximation algorithm that works for all graphs was known prior to this work.
Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) ...
详细信息
ISBN:
(纸本)9781509053360
Distributed cloud networking builds on network functions virtualization (NFV) and software defined networking (SDN) to enable the deployment of network services in the form of elastic virtual network functions (VNFs) instantiated over general purpose servers at distributed cloud locations. We address the design of fast approximation algorithms for the NFV service distribution problem (NSDP), whose goal is to determine the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a queue-length based algorithm, named QNSD, that provides an O (is an element of) approximation in time O (1/is an element of). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.
We consider the weight-reducible knapsack problem, where we are given a limited budget that can be used to decrease item weights, and we would like to optimize the knapsack objective value using such weight improvemen...
详细信息
ISBN:
(纸本)9783319060897;9783319060880
We consider the weight-reducible knapsack problem, where we are given a limited budget that can be used to decrease item weights, and we would like to optimize the knapsack objective value using such weight improvements. We develop a pseudo-polynomial algorithm for the problem, as well as a polynomial-time 3-approximation algorithm based on solving the LP-relaxation. Furthermore, we consider the special case of one degree of improvement with equal improvement costs for each item, and present a linear-time 3-approximation algorithm based on solving a cardinality-constrained and a classic knapsack problem, and show that the analysis of the polynomial-time 3-approximation algorithm can be improved to yield a 2-approximation.
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is ...
详细信息
ISBN:
(纸本)9781605586069
We consider the problem of time-constrained scheduling of packets in a communication network. Each packet has, in addition to its source and its destination, a release time and a deadline. The goal of an algorithm is to maximize the number of packets that arrive to their destinations by their respective deadlines, given the network constraints. We consider the line network, and a setting where each node has a buffer of size B packets (where B can be finite or infinite), and each edge has capacity C >= 1. To the best of our knowledge this is the first work to study time-constrained scheduling in a setting when buffers can be of limited size. We give approximation algorithms that achieve (expected) approximation ratio of O(max{log* n - log* B, 1} + max{log* Sigma - log* C, 1}), where n is the length of the line, and E is the maximum slack a message can have (the slack is the number of time steps a message can be idle and still arrive within its deadline). A special case of our setting is the setting of buffers of unlimited capacity and edge capacities 1, which has been previously studied by Adler et al. [2]. For this case our results considerably improve upon previous results: Via a slight modification of our algorithms we also obtain an approximation ratio of O(min{log* n, log* Sigma, log* M}) (where M is the number of messages in the instance), which is a significant improvement upon the results of Adler et al.
We present algorithms with poly-logarithmic approximation ratios for the buy-at-bulk network design problem in the node-weighted setting. We obtain the following results where h is the number of pairs in the input. An...
详细信息
ISBN:
(纸本)9780898716245
We present algorithms with poly-logarithmic approximation ratios for the buy-at-bulk network design problem in the node-weighted setting. We obtain the following results where h is the number of pairs in the input. An O(log h) approximation for the single-sink non-uniform buy-at-bulk network design. Unless P = NP this ratio is tight up to constant factors. An O(log(4) h) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.
暂无评论