190 research outputs found
A Relaxed FPTAS for Chance-Constrained Knapsack
No full textThe stochastic knapsack problem is a stochastic version of the well known deterministic knapsack problem, in which some of the input values are random variables. There are several variants of the stochastic problem. In this paper we concentrate on the chance-constrained variant, where item values are deterministic and item sizes are stochastic. The goal is to find a maximum value allocation subject to the constraint that the overflow probability is at most a given value. Previous work showed a PTAS for the problem for various distributions (Poisson, Exponential, Bernoulli and Normal). Some strictly respect the constraint and some relax the constraint by a factor of (1+epsilon). All algorithms use Omega(n^{1/epsilon}) time. A very recent work showed a "almost FPTAS" algorithm for Bernoulli distributions with O(poly(n) * quasipoly(1/epsilon)) time.
In this paper we present a FPTAS for normal distributions with a solution that satisfies the chance constraint in a relaxed sense. The normal distribution is particularly important, because by the Berry-Esseen theorem, an algorithm solving the normal distribution also solves, under mild conditions, arbitrary independent distributions. To the best of our knowledge, this is the first (relaxed or non-relaxed) FPTAS for the problem. In fact, our algorithm runs in poly(n/epsilon) time. We achieve the FPTAS by a delicate combination of previous techniques plus a new alternative solution to the non-heavy elements that is based on a non-convex program with a simple structure and an O(n^2 log {n/epsilon}) running time. We believe this part is also interesting on its own right
A Practical Revocation Scheme for Broadcast Encryption Using Smart Cards (Extended Abstract)
No full textNoam Kogan y Yuval Shavitt z Avishai Wool x Abstract We present an anti-pirate revocation scheme for broadcast encryption systems (e.g., pay TV), in which the data is encrypted to ensure payment by users. In the systems we consider, decryption of keys is done on smartcards, and key management is done in-band. Our starting point is recent scheme of Naor and Pinkas. The basic scheme uses secret sharing to remove up to t parties, is information theoretic secure against coalitions of size t, and is capable of creating a new group key. However, with current smartcard technology, this scheme is only feasible for small system parameters, allowing up to about 100 pirates to be revoked before all the smartcards need to be replaced
A Systematic Investigation of the Active Space Requirements for the Computation of Accurate Spectroscopic Constants for State Specific Multireference Perturbation Theory
No full text I. Shavitt, E. A. Stahlberg, International Sanibel Symposium on Atomic, Molecular, and Condensed Matter Theory, St. Augustine, Florida, March 1992.Author Institution: Department of Chemistry and The Laser Spectroscopy Facility, The Ohio State UniversityThe recent formulation and implementation of State Specific Multireference Perturbation allows for the treatment of dynamic and non-dynamic electron correlation for systems which are too large to be treated by other Multireference methods. It also allows for the treatment of dynamic and non-dynamic electron correlation of states which are inaccessible to single reference methodologies, such as low spin singlets and doublets. This talk will focus on the active space requirements for the accurate computation of and for the low spin doublet states of some simple diatomics. The active space requirements for MRACPF, MRCISD, and MRPT methodologies will be compared
Efficient Bandwidth Release After Failures in ATM Networks
No full textWhen a connection is established in an ATM network, resources are allocated to guarantee an appropriate grade of service. When a failure occurs in a link or a node, many connections are simultaneously disrupted. We present an algorithm that efficiently releases the resources that are allocated to these broken connections. Moreover, our algorithm does not require the switches to store explicit bandwidth information about all individual connection they switch and thus results in simpler and cheaper switch design. Key words: ATM, bandwidth release, failures. October 1995 CC PUB #116 Dept. of Electrical Engineering Technion, Haifa, Israel. Corresponding author 1 Introduction Communication in ATM is connection oriented, i.e., before data can be transmitted, a connection must be established. Connections are defined in two levels: virtual path (VP) and virtual channel (VC). A virtual path is, similar to a virtual circuit in traditional networks, a concatenation of physical links that s..
On the Economics of Multicasting
No full textA supplier of multicast information services will often be faced with the following problem: Broadcasting to the whole customer base (including non-paying customers) is cheaper than multicasting only to the paying customers. However, broadcasting discourages potential customers from paying. The result is an economic game in which the supplier tries to maximize profit in the face of rational, but not omniscient, behavior by customers
Achieving bursty traffic guarantees by integrating traffic engineering and buffer management tools
No full textTraffic engineering tools are applied to design a set of paths, e.g., using MPLS, in the network in order to achieve global network utilization. Usually, paths are guaranteed long-term traffic rates, while the short-term rates of bursty traffic are not guaranteed. The resource allocation scheme, suggested in this paper, handles bursts based on maximal traffic volume allocation (termed TVAfB) instead of a single maximal or sustained rate allocation. This translates to better SLAs to the network customers, namely SLAs with higher traffic peaks, that guarantees burst non-dropping. Given a set of paths and bandwidth allocation along them, the suggested algorithm finds a special collection of bottleneck links, which we term the first cut, as the optimal buffering location for bursts. In these locations, the buffers act as an additional resource to improve the network short-term behavior, allowing traffic to take advantage of the under-used resources at the links that precede and follow the bottleneck links. The algorithm was implemented in MATLAB. The resulted provisioning parameters were simulated using NS-2 to demonstrate the effectiveness of the proposed scheme
Limitations and Possibilities of Path Trading between Autonomous Systems
No full textWhen forwarding packets in the Internet, Autonomous Systems (ASes) frequently choose the shortest path in their network to the next-hop AS in the BGP path, a strategy known as hot-potato routing. As a result, paths in the Internet are suboptimal from a global perspective. For peering ASes who exchange traffic without payments, path trading - complementary deviations from hot- potato routing - appears to be a desirable solution to deal with these inefficiencies. In recent years, path trading approaches have been suggested as means for interdomain traffic engineering between neighboring ASes, as well as between multiple ASes to achieve global efficiency. Surprisingly, little is known on the computational complexity of finding path trading solutions, or the conditions which guarantee the optimality or even approximability of a path trading protocol. In this paper we explore the computational feasibility of computing path trading solutions between peering ASes. We first show that finding a path trading solution between a pair of ASes is NP- complete, and that path-trading solutions are even NP-hard to approximate. We continue to explore the feasibility of implementing policies between multiple ASes and show that, even if the bilateral path trading problem is tractable for every AS pair in the set of trading ASes, path trading between multiple ASes is NP- hard, and NP-hard to approximate as well. Despite the above negative results, we show a pseudo-polynomial algorithm to compute path trading solutions. Thus, if the range of the instances is bounded, we show one can compute solutions efficiently for peering ASes. We evaluate the path trading algorithm on pairs of ASes using real network topologies. Specifically, we use real PoP-level maps of ASes in the Internet to show that path trading can substantially mitigate the inefficiencies associated with hot-potato routing
Maximum flow routing with weighted max-min fairness
No full textAbstract. Max-min is an established fairness criteria for allocating bandwidthfor flows. In this work we look at the combined problem of routing and bandwidth allocation such that the flow allocation for each connection will be max-imized and fairness will be maintained. We use the weighted extension of the max-min criteria to allocate bandwidth proportionaly to the flows ' demand. Ourcontribution is an algorithm which, for the first time, solve the combined routing and bandwidth allocation problem for the case where flows are allowed tobe splitted along several paths. We use multi commodity flow (MCF) formulation which is solved using linear programming (LP) techniques. These building blocksare used by our algorithm to derive the required optimal routing and allocation. 1 Introduction Traffic engineering is a paradigm where network operators control the traffic and al-locate resources in order to achieve goals such as, maximum flow or minimum delay. One challenge is to allow different flows to share the network, so that the total flow willbe maximized while fairness will be preserved. Given a network, and a set of demands between its nodes, a network operator may wish to maximize their profit by routingthe traffic so it will maximize the total allocated bandwidth the network can carry, or namely the total assigned net flow. To do this we allow flows to be arbitrarily split insidethe network. One way to maximize the network flow is to formulate it as a maximum multi-commodity flow (MCF) problem which can be solved using linear programming (LP). While the solution will maximize the flow, it will not always do it in a fair manner.Flows that traverse several congested links will be allocated very little bandwidth or non at all, while flows that traverse short hop distances will receive a large allocation ofbandwidth
- …
