Concept
Majorant ou minorant
Publications associées (171)
Hypergraphic LP Relaxations for Steiner Trees
We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Koenemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this ...
Springer2010Partitioning Datasets Based on Equalities Among Parameters
When a phenomenon is described by a parametric model and multiple datasets are available, a key problem in statistics is to discover which datasets are characterized by the same parameter values. Equivalently, one is interested in partitioning the family o ...
2009Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
Rachid Guerraoui, Seth Gilbert, Dan Alistarh
Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal ...
Springer2009Approximating the Gaussian Multiple Description Rate Region Under Symmetric Distortion
We consider multiple description (MD) coding for the Gaussian source with K descriptions under the symmetric mean-squared error (MSE) distortion constraints, and provide an approximate characterization of the rate region. We show that the rate region can b ...
2009Improved successive constraint method based a posteriori error estimate for reduced basis approximation of 2D Maxwell's problem
Jan Sickmann Hesthaven, Yvon Maday
In a posteriori error analysis of reduced basis approximations to affinely parametrized partial differential equations, the construction of lower bounds for the coercivity and inf-sup stability constants is essential. In [Huynh et al., C. R. Acad. Sci. Par ...
EDP SCIENCES S A2009An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-time Scheduling
We introduce the "First Fit Matching Periods" algorithm for static-priority multiprocessor scheduling of periodic tasks with implicit deadlines and show that it yields asymptotically optimal processor assignments if utilization values are chosen uniformly ...
Springer2009Weighted A* search - unifying view and application
The A* algorithm is a well-known heuristic best-first search method. Several performance-accelerated extensions of the exact A* approach are known. Interesting examples are approximate algorithms where the heuristic function used is inflated by a weight (o ...
2009Convexity bounds for BSDE solutions, with applications to indifference valuation
Christoph Frei, Semyon Malamud
We consider backward stochastic differential equations (BSDEs) with a particular quadratic generator and study the behaviour of their solu- tions when the probability measure is changed, the filtration is shrunk, or the underlying probability space is transf ...
2009Faster Integer Multiplication
For more than 35 years, the fastest known method for integer multiplication has been the Schonhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions, there is a corresponding Omega(n log n) lower bound. All this ...
2009