Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating Two-Stage Stochastic Supplier Problems
220
0
0.0
(
0
)
Added by
Leonidas Tsepenekas
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The main focus of this paper is radius-based (supplier) clustering in the two-stage stochastic setting with recourse, where the inherent stochasticity of the model comes in the form of a budget constraint. We also explore a number of variants where additional constraints are imposed on the first-stage decisions, specifically matroid and multi-knapsack constraints. Our eventual goal is to provide results for supplier problems in the most general distributional setting, where there is only black-box access to the underlying distribution. To that end, we follow a two-step approach. First, we develop algorithms for a restricted version of each problem, in which all possible scenarios are explicitly provided; second, we employ a novel emph{scenario-discarding} variant of the standard emph{Sample Average Approximation (SAA)} method, in which we crucially exploit properties of the restricted-case algorithms. We finally note that the scenario-discarding modification to the SAA method is necessary in order to optimize over the radius.
rate research
Read More
We consider the problem of approximately solving constraint satisfaction problems with arity $k > 2$ ($k$-CSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of $k$-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of high-dimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter $gamma$ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet $[q]$ is a high-dimensional expander with parameter $gamma$, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error $epsilon$ using $q^{O(k)} cdot (k/epsilon)^{O(1)}$ levels of the sum-of-squares SDP hierarchy, provided $gamma leq epsilon^{O(1)} cdot (1/(kq))^{O(k)}$. Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank $r$ for a threshold $tau = (epsilon/k)^{O(1)} cdot (1/q)^{O(k)}$, then it is possible to approximately solve the instance up to additive error $epsilon$, using $r cdot q^{O(k)} cdot (k/epsilon)^{O(1)}$ levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small $gamma$) have threshold rank 1 according to our definition.
In this paper, we propose a discretization scheme for the two-stage stochastic linear complementarity problem (LCP) where the underlying random data are continuously distributed. Under some moderate conditions, we derive qualitative and quantitative convergence for the solutions obtained from solving the discretized two-stage stochastic LCP (SLCP). We explain how the discretized two-stage SLCP may be solved by the well-known progressive hedging method (PHM). Moreover, we extend the discussion by considering a two-stage distributionally robust LCP (DRLCP) with moment constraints and proposing a discretization scheme for the DRLCP. As an application, we show how the SLCP and DRLCP models can be used to study equilibrium arising from two-stage duopoly game where each player plans to set up its optimal capacity at present with anticipated competition for production in future.
Two-stage optimization with recourse model is an important and widely used model, which has been studied extensively these years. In this article, we will look at a new variant of it, called the two-stage optimization with recourse and revocation model. This new model differs from the traditional one in that one is allowed to revoke some of his earlier decisions and withdraw part of the earlier costs, which is not unlikely in many real applications, and is therefore considered to be more realistic under many situations. We will adopt several approaches to study this model. In fact, we will develop an LP rounding scheme for some cover problems and show that they can be solved using this scheme and an adaptation of the rounding approach for the deterministic counterpart, provided the polynomial scenario assumption. Stochastic uncapacitated facility location problem will also be studied to show that the approximation algorithm that worked for the two-stage with recourse model worked for this model as well. In addition, we will use other methods to study the model.
We study the {em min-cost chain-constrained spanning-tree} (abbreviated mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {em unweighted} cst was known cite{olver}, which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an $O(1)$-factor for {em both} the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we {em reduce} mcst to unweighted cst (and then utilize cite{olver}) via a novel application of {em Lagrangian duality} to simplify the {em cost structure} of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the {em $k$-budgeted matroid basis} problem, where we build upon a recent rounding algorithm of cite{BansalN16} to obtain an improved $n^{O(k^{1.5}/epsilon)}$-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a $(1+epsilon)$-violation of the other budget constraints.
A sketch is a probabilistic data structure used to record frequencies of items in a multi-set. Sketches are widely used in various fields, especially those that involve processing and storing data streams. In streaming applications with high data rates, a sketch fills up very quickly. Thus, its contents are periodically transferred to the remote collector, which is responsible for answering queries. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a significantly higher accuracy compared to prior art, a much smaller memory footprint, and at the same time achieves the same speed as the best prior sketch. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slim-subsketch and a large sketch called Fat-subsketch. The Slim-subsketch is periodically transferred to the remote collector for answering queries quickly and accurately. The Fat-subsketch, however, is not transferred to the remote collector because it is used only to assist the Slim-subsketch during the insertions and deletions and is not used to answer queries. We implemented and extensively evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch outperforms the most widely used CM-sketch by up to 33.1 times in terms of accuracy. We have released the source codes of our proposed sketch as well as existing sketches at Github. The short version of this paper will appear in ICDE 2017.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
