Nir Halman

TCS Journal 2025 Journal Article

Packing squares independently

• Wei Wu
• Hiroki Numaguchi
• Nir Halman
• Yannan Hu
• Mutsunori Yagiura

Given a set of squares and a strip with bounded width and infinite height, we consider a square strip packaging problem, which we call the square independent packing problem (SIPP), to minimize the strip height so that all the squares are packed into independent cells separated by horizontal and vertical partitions. For the SIPP, we first investigate efficient solution representations and propose a compact representation that reduces the search space from Ω ( n! ) to O ( 2 n ), with n the number of given squares, while guaranteeing that there exists a solution representation that corresponds to an optimal solution. Based on the solution representation, we show that the problem is NP -hard. To solve the SIPP, we propose a dynamic programming method that can be extended to a fully polynomial-time approximation scheme (FPTAS). We also propose three mathematical programming formulations based on different solution representations and confirm their performance through computational experiments with a mathematical programming solver. Finally, we discuss several extensions that are relevant to practical applications.

TCS Journal 2016 Journal Article

A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy

• Nir Halman

Given n elements with nonnegative integer weights w = ( w 1, …, w n ), an integer capacity C and positive integer ranges u = ( u 1, …, u n ), we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most C. We give a deterministic algorithm that estimates the number of solutions to within relative error ϵ in time polynomial in n, log ⁡ U and 1 / ϵ, where U = max i ⁡ u i. More precisely, our algorithm runs in O ( n 3 log 2 ⁡ U ϵ log ⁡ n log ⁡ U ϵ ) time. This is an improvement of n 2 and 1 / ϵ (up to log terms) over the best known deterministic algorithm by Gopalan et al. (2011) [5]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of binding constraints.

SODA Conference 2008 Conference Paper

Fully polynomial time approximation schemes for stochastic dynamic programs

• Nir Halman
• Diego Klabjan
• Chung-Lun Li
• James B. Orlin
• David Simchi-Levi

FOCS Conference 2004 Conference Paper

On the Power of Discrete and of Lexicographic Helly-Type Theorems

• Nir Halman

Helly's theorem says that if every d + 1 elements of a given finite set of convex objects in /spl Ropf//sup d/ have a common point, then there is a point common to all of the objects in the set. We define three types of Helly theorems: discrete Helly theorems - where the common point should belong to an a-priori given set, lexicographic Helly theorems - where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We show the relations between these Helly theorems and their corresponding (standard) Helly theorems. We obtain several discrete and lexicographic Helly numbers. Using these types of Helly theorems we get linear time solutions for various optimization problems. For this, we define a framework, DLP-type (discrete linear programming type), and provide algorithms that solve in randomized linear time fixed-dimensional DLP-type problems. We show that the complexity of the DLP-type class stands somewhere between linear programming (LP) and integer programming (IP). Finally, we use our results in order to solve in randomized linear time problems such as the discrete p-center on the real line, the discrete weighted 1-center problem in /spl Ropf//sup d/ with l/sub /spl infin// norm, the standard (continuous) problem of finding a line transversal for a totally separable set of planar convex objects, a discrete version of the problem of finding a line transversal for a set of axis-parallel planar rectangles, and the (planar) lexicographic rectilinear p-center problem for p = 1, 2, 3. These are the first known linear time algorithms for these problems.