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 ...
详细信息
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. There has been almost no prior work however on developing approximation algorithms for distributionally robust problems, when the underlying scenario-set is discrete, as is the case with discrete-optimization problems. 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. This follows because we argue that a distributionally robust problem can be reduced in a novel way to a standard 2-stage problem with bounded inflation factor, which enables one to use the SAA machinery developed for 2-stage problems. Complementing this, we show how to approximately solve a fractional relaxation of the SAA (i.e., polynomial-scenario central-distribution) problem. Unlike in
In this paper we consider the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short) and an integer B, the objective is to find a mapping of its nodes into blo...
详细信息
ISBN:
(纸本)9783319951652;9783319951645
In this paper we consider the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short) and an integer B, the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. This paper focuses on the case B = 2. Even if B = 2 and the height of the DAG is three, it is known that the problem is NP-hard, and furthermore, there is no 3/2 - epsilon factor approximation algorithm for B = 2 and a small positive epsilon unless P = NP. On the other hand, the best approximation ratio previously shown is 3. In this paper we improve the approximation ratio into strictly smaller than 2. Also, we investigate the relationship between the height of input DAGs and the inapproximability, since the above inapproximability bound 3/2 - epsilon is shown only for DAGs of height 3.
The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense ...
详细信息
We study a natural model of coordinated social ad campaigns over a social network, based on models of Datta et al. and Aslay et al. Multiple advertisers are willing to pay the host — up to a known budget — per user ...
详细信息
Given a simple connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that...
详细信息
This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle a and height H when their apex points lie on a planar surface. This is a novel variant of the 3...
详细信息
ISBN:
(纸本)9781538630815
This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle a and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-TSPN. When the cones are allowed to tilt by an angle epsilon we have the tilted Cone-TSPN problem, to which we present an algorithm that returns a solution with an approximation ratio of O (1+tan alpha / 1-tan epsilon tan alpha (1 + log max(H)/min(H)). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.
X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin--Courant r...
详细信息
ISBN:
(纸本)9781450363099
X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin--Courant rule. We show how to use the GreedyMonroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin--Courant rule, by appropriately setting a "schedule" for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.
We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem (also called the traveling deliveryman or minimum latency problem). Given a metric (V;d) w...
详细信息
Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manu...
详细信息
Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This prob...
详细信息
暂无评论