๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Multilinear approximation on rectangles and the related moment problem

โœ Scribed by Willem K. Klein Haneveld

Book ID
118713158
Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
211 KB
Volume
59
Category
Article
ISSN
0039-0402

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On Approximating the Depth and Related P
On Approximating the Depth and Related Problems
โœ Aronov, Boris; Har-Peled, Sariel ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› Society for Industrial and Applied Mathematics ๐ŸŒ English โš– 332 KB
Constant Ratio Approximation Algorithms
Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
โœ Daya Ram Gaur; Toshihide Ibaraki; Ramesh Krishnamurti ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 114 KB

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the m

On the approximability of clique and rel
On the approximability of clique and related maximization problems
โœ Aravind Srinivasan ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 247 KB

We consider approximations of the form n 1ร€oรฐ1รž for the Maximum Clique problem, where n is the number of vertices in the input graph and where the ''oรฐ1รž'' term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability re