Displaying similar documents to “Tail approximations for samples from a finite population with applications to permutation tests”

Tail approximations for samples from a finite population with applications to permutation tests

Zhishui Hu, John Robinson, Qiying Wang (2012)

ESAIM: Probability and Statistics

Similarity:

This paper derives an explicit approximation for the tail probability of a sum of sample values taken without replacement from an unrestricted finite population. The approximation is shown to hold under no conditions in a wide range with relative error given in terms of the standardized absolute third moment of the population, . This approximation is used to obtain a result comparable to the well-known Cramér large deviation result...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2010)

RAIRO - Operations Research

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem  which only differ on a linear transformation of their objective functions. This...

Fixed-α and fixed-β efficiencies

Christopher S. Withers, Saralees Nadarajah (2013)

ESAIM: Probability and Statistics

Similarity:

Consider testing :  ∈  against :  ∈  for a random sample , ..., from , where and are two disjoint sets of cdfs on ℝ = (−∞, ∞). Two non-local types of efficiencies, referred to as the fixed- and fixed- efficiencies, are introduced for this two-hypothesis testing situation. Theoretical tools are developed to evaluate these efficiencies for some of the most...

Cramér type moderate deviations for Studentized U-statistics

Tze Leng Lai, Qi-Man Shao, Qiying Wang (2011)

ESAIM: Probability and Statistics

Similarity:

Let be a Studentized U-statistic. It is proved that a Cramér type moderate deviation ( ≥ )/(1 − Φ()) → 1 holds uniformly in ∈ [0, ( )) when the kernel satisfies some regular conditions.

Fast approximation of minimum multicast congestion – Implementation VERSUS Theory

Andreas Baltz, Anand Srivastav (2010)

RAIRO - Operations Research

Similarity:

The problem of minimizing the maximum edge congestion in a multicast communication network generalizes the well-known -hard multicommodity flow problem. We give the presently best theoretical approximation results as well as efficient implementations. In particular we show that for a network with edges and multicast requests, an OPT + exp(1)ln)-approximation can be computed in lnln) time, where  bounds the time for computing an -approximate minimum Steiner tree. Moreover, we present...

A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira, Eduardo Candido Xavier, Flávio Keidi Miyazawa (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin , and a list of rectangular items, each item with a class value in {1,...,}. The problem is to pack a subset of into , maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item , items with higher class values can not block . We present a (4 + )-approximation algorithm when the bin is a square. We also present (3 + )-approximation...

On the Average Case Complexity of Some P-complete Problems

Maria Serna, Fatos Xhafa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that some classical P-complete problems can be solved efficiently in NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by ( ln 4 + (1))log , asymptotically with high probability, where is the instance size.

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....

Adaptive non-asymptotic confidence balls in density estimation

Matthieu Lerasle (2012)

ESAIM: Probability and Statistics

Similarity:

We build confidence balls for the common density of a real valued sample . We use resampling methods to estimate the projection of onto finite dimensional linear spaces and a model selection procedure to choose an optimal approximation space. The covering property is ensured for all  ≥ 2 and the balls are adaptive over a collection of linear spaces.

Adaptive non-asymptotic confidence balls in density estimation

Matthieu Lerasle (2012)

ESAIM: Probability and Statistics

Similarity:

We build confidence balls for the common density of a real valued sample . We use resampling methods to estimate the projection of onto finite dimensional linear spaces and a model selection procedure to choose an optimal approximation space. The covering property is ensured for all  ≥ 2 and the balls are adaptive over a collection of linear spaces.

Nash equilibria for a model of traffic flow with several groups of drivers

Alberto Bressan, Ke Han (2012)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

Traffic flow is modeled by a conservation law describing the density of cars. It is assumed that each driver chooses his own departure time in order to minimize the sum of a departure and an arrival cost. There are groups of drivers, The -th group consists of drivers, sharing the same departure and arrival costs (), (). For any given population sizes ,, , we prove the existence of a Nash equilibrium solution,...

Simulation and approximation of Lévy-driven stochastic differential equations

Nicolas Fournier (2011)

ESAIM: Probability and Statistics

Similarity:

We consider the approximate Euler scheme for Lévy-driven stochastic differential equations. We study the rate of convergence in law of the paths. We show that when approximating the small jumps by Gaussian variables, the convergence is much faster than when simply neglecting them. For example, when the Lévy measure of the driving process behaves like ||d near , for some ∈ (1,2), we obtain an error of order 1/√ with a computational cost of order . For a similar error when neglecting...