Paz Carmi

TCS Journal 2024 Journal Article

Dynamic Euclidean bottleneck matching

• A. Karim Abu-Affash
• Sujoy Bhore
• Paz Carmi

A fundamental question in computational geometry is for a set of input points in the Euclidean space, that is subject to discrete changes (insertion/deletion of points at each time step), whether it is possible to maintain an exact/approximate minimum weight perfect matching and/or bottleneck matching (a perfect matching that minimizes the length of the longest matched edge), in sublinear update time. In this work, we answer this question in the affirmative for points on a real line and for points in the plane with a bounded geometric spread. For a set P of n points on a line, we show that there exists a dynamic algorithm that maintains an exact bottleneck matching of P and supports insertion and deletion in O ( log ⁡ n ) time. Moreover, we show that a modified version of this algorithm maintains an exact minimum-weight perfect matching with O ( log ⁡ n ) update (insertion and deletion) time. Next, for a set P of n points in the plane, we show that a ( 6 2 )-factor approximate bottleneck matching of P k, at each time step k, can be maintained in O ( log ⁡ Δ ) amortized time per insertion and O ( log ⁡ Δ + | P k | ) amortized time per deletion, where Δ is the geometric spread of P (the ratio between the diameter of P and the distance between the closest pair of points in P).

TCS Journal 2021 Journal Article

Minimizing total interference in asymmetric sensor networks

• A. Karim Abu-Affash
• Paz Carmi
• Matthew J. Katz

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized. For the one-dimensional case, we show how to solve the problem optimally in O ( n 3 ) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.

TCS Journal 2019 Journal Article

Approximability of covering cells with line segments

• Paz Carmi
• Anil Maheshwari
• Saeed Mehrabi
• Luís Fernando Schultz Xavier da Silveira

Korman et al. [18] studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP -hard, even if the line segments in S are axis-parallel, and it remains NP -hard when the goal is to cover the “rectangular” cells (i. e. , cells that are defined by exactly four axis-parallel line segments). In this paper, we consider the approximability of the problem. We first give a PTAS for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is APX -hard. We also consider the parameterized complexity of the problem and prove that the problem is FPT when parameterized by the size of an optimal solution. Our FPT algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [18] in which the goal is to cover the “rectangular” cells.

SODA Conference 2015 Conference Paper

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

• Greg Aloupis
• Luis Barba
• Paz Carmi
• Vida Dujmovic
• Fabrizio Frati
• Pat Morin

TCS Journal 2009 Journal Article

Matrix columns allocation problems

• Amos Beimel
• Boaz Ben-Moshe
• Yehuda Ben-Shimol
• Paz Carmi
• Eldad Chai
• Itzik Kitroser
• Eran Omri

Orthogonal Frequency Division Multiple Access (OFDMA) transmission technique is gaining popularity as a preferred technique in the emerging broadband wireless access standards. Motivated by the OFDMA transmission technique we define the following problem: Let M be a matrix (over R ) of size a × b. Given a vector of non-negative integers C → = 〈 c 1, c 2, …, c b 〉 such that ∑ c j = a, we would like to allocate a cells in M such that (i) in each row of M there is a single allocation, and (ii) for each element c i ∈ C → there is a unique column in M which contains exactly c i allocations. Our goal is to find an allocation with minimal value, that is, the sum of all the a cells of M which were allocated is minimal. The nature of the suggested new problem is investigated in this paper. Efficient algorithms are suggested for some interesting cases. For other cases of the problem, NP-hardness proofs are given followed by inapproximability results.

STOC Conference 2006 Conference Paper

Private approximation of search problems

• Amos Beimel
• Paz Carmi
• Kobbi Nissim
• Enav Weinreb

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions . Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.