Catálogo de publicaciones - libros

Partitioning a multi-dimensional data set (array) into rectangular regions subject to some constraints (error measures) is an important problem arising from applications in parallel computing, databases, VLSI design, and so on. In this paper, we consider two most common types of partitioning used in practice: the Arbitrary partitioning and (×) partitioning, and study their relationships under three widely used error metrics: Max-Sum, Sum-SVar and Sum-SLift.

This paper presents an algorithm to generate quality tetrahedral meshes for the volumes bounded by the molecular skin model defined by Edelsbrunner. The algorithm applies the Delaunay refinement to the tetrahedral meshes bounded by quality surface meshes. In particular, we iteratively insert the circumcenters of bad shape tetrahedra with a priority parameterized by its distance from the surface. We achieve a bounded radius-edge ratio for the tetrahedral mesh after the refinement. Finally, we apply the sliver exudation algorithm to remove ‘slivers’. The algorithm terminates with guarantees on the tetrahedral quality and an accurate approximation of the original surface boundary.

In the TSP with neighborhoods problem we are given a set of regions (neighborhoods) in the plane, and seek to find a minimum length TSP tour that goes through all the regions. We give two approximation algorithms for the case when the regions are allowed to intersect: We give the first (1)-factor approximation algorithm for intersecting convex fat objects of comparable diameters where we are allowed to hit each object only at a finite set of specified points. The proof follows from two packing lemmas that are of independent interest. For the problem in its most general form (but without the specified points restriction) we give a simple (log)-approximation algorithm.

We give improved lower bounds for the size of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs ,..., and outputs ¬,...,¬. We show that (1) For =2–1, circuits computing Parity with –1 NOT gates have size at least 6–log(+1)–(1) and (2) For =2–1, inverters with NOT gates have size at least 8–log(+1)–(1). We derive our bounds above by considering the minimum size of a circuit with at most NOT gates that computes Parity for inputs ≥⋯≥. For an , we completely determine the minimum size. For odd , it is 2––2 for ⌈log(+1)⌉–1≤ ≤/2, and it is for ≥/2. We also determine the minimum size of an with at most  NOT gates. It is 4–3 for ⌈log(+1) ⌉≤ ≤. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments.

Motivated by Papadimitriou and Yannakakis’ paper on limited nondeterminism [19], we study two questions arising from their work: and the for groups and quasigroups.

In this paper we show that the inverse problems of HAMILTONIAN CYCLE and 3-D MATCHING are coNP complete. This completes the study of inverse problems of the six natural NP-complete problems from [2] and answers an open question from [1]. We classify the inverse complexity of the natural verifier for HAMILTONIAN CYCLE and 3-D MATCHING by showing coNP-completeness of the corresponding inverse problems.

A (,)-tuple is a word of length on an alphabet of size . A graph is (,)-representable if we can assign a (,)-tuple to each vertex such that two vertices are connected iff the associated tuples agree on some component. We study the complexity of several graph problems on (,)-representable graphs, as a function of the parameters ,; the problems under study are , and . In this framework, there are two classes of interest: the graphs representable with tuples of logarithmic length (i.e. graphs (,)-representable with = ( log)), and the graphs representable with tuples of polynomial length (i.e. graphs (,)-representable with = ()). In both cases, we show that the problems are computationally hard, though we obtain stronger hardness results in the second case. Our hardness results also allow us to derive optimality results for and .

A codeword tester is a highly query-efficient spot checking procedure for ascertaining, with good confidence, proximity of a given string to its closest codeword. We consider the problem of binary codeword testing using only two queries. It is known that three queries suffice for non-trivial codeword testing with perfect completeness (where codewords must be accepted with probability 1). It is known that two queries are not enough for testing with perfect completeness, whereas two queries suffice if one relaxes the requirement of perfect completeness (this is akin to the polynomial-time decidability of 2SAT and the APX-hardness of Max 2SAT, respectively).

In this work, motivated by the parallel with 2-query PCPs and the approximability of near-satisfiable instances of Max 2SAT, we investigate 2-query testing with completeness close to 1, say 1– for →0. Our result is that, for codes of constant relative distance, such testers must also have soundness 1– () (and this is tight up to constant factors in the () term). This is to be contrasted with 2-query PCPs, where assuming the Unique Games Conjecture, one can have completeness 1– and soundness . Hence the ratio (1–)/(1–) can be super-constant for 2-query PCPs while it is bounded by a constant for 2-query LTCs. Our result also shows a similar limitation of 2-query PCPs of proximity, a notion introduced in [1].

We introduce a new (lg lg )-competitive binary search tree data structure called poketree that has the advantage of attaining, under worst-case analysis, (lg ) cost per operation, including updates. Previous (lg lg )-competitive binary search tree data structures have not achieved (lg ) worst-case cost per operation. A standard data structure such as red-black tree or deterministic skip list can be augmented with the dynamic links of a poketree to make it (lg lg n)-competitive. Our approach also uses less memory per node than previous competitive data structures supporting updates.

In this paper, we study several interesting problems in -D ( ≥3) discrete geometric spaces, which arise in high dimensional medical image segmentation. Given a -D voxel grid of cells, two classes of geometric regions that are enclosed by a single or two coupled smooth defined on the entire grid domain are considered. The objective functions are normalized by a function of the desired regions, which avoids a bias to produce an overly large or small region resulting from data noise. The normalization functions that we employ are used in real medical image segmentation. To our best knowledge, no previous results on these problems in high dimensions are known. We develop a unified algorithmic framework based on a careful characterization of the intrinsic geometric structures and a nontrivial graph transformation scheme, yielding efficient polynomial time algorithms for solving these ORD problems. Our main ideas include the following. We show that the optimal solution to the ORD problems can be obtained via the construction of a convex hull for a set of () unknown 2-D points using the hand probing technique. The probing oracles are implemented by computing a minimum - cut in a weighted directed graph. The ORD problems are then solved by () calls to the minimum - cut algorithm. For the class of regions bounded by a single heighfield surface, our further investigation shows that the () calls to the minimum - cut algorithm are on a monotone parametric flow network, which enables to detect the optimal-ratio region in the complexity of computing a single maximum flow.