Vi tillhandahåller konstant förhållande approximation algoritmer för två NP-hårda problem, rektangeln sticka problem och rektilinear partitionering problem. I rektangelstockningsproblemet får vi en uppsättning rektanglar i tvådimensionellt utrymme, med målet att sticka alla rektanglar med minsta antal linjer parallella med x- och y-axlarna. Vi ger en 2- approximation algoritm, medan den mest kända approximation förhållandet för detta problem är O log n. Denna algoritm utvidgas sedan till en 4- approximation algoritm för rektilinear partitionering problem, som, med tanke på en m x × m y array av icke-negativa heltal och positiva heltal v h, ber att hitta en uppsättning v vertikala och h horisontella linjer sådan att den maximala belastningen av en subrektangel (dvs, summan av siffrorna i det) minimeras. Det mest kända approximationsförhållandet för detta problem är 27. Vår approximation förhållande 4 är nära till bästa möjliga, eftersom det är känt att vara NP-hård till approximation inom någon faktor mindre än 2. Resultaten utvidgas sedan till det d-dimensionella utrymmet för d ≥ 2, där a
De tillhandahöll också en (ρ+1 ρ ) - approximation algoritm för rs (med krav) genom att utöka algoritmen för rs från REF.
Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
{'venue': 'J. Algorithms', 'journal': 'J. Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}