Catálogo de publicaciones - libros

We consider the problem of packing a set of weighted rectangles into a unit size square frame [0,1] × [0,1] so as to maximize the total weight of the packed rectangles. We present polynomial time approximation schemes (PTASs) that, for any >0, find (1 - )-approximate solutions for two special cases of the problem. In the first case we pack a set of squares whose weights are equal to their areas. In the second case we pack a set of weighted rectangles into an augmented square frame [0,1 + 3] × [0,1 + 3].

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game- theoretic approach and graph decompositions called tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of -branched tree decompositions. The equivalence between nondeterministic graph searching and -branched tree decomposition enables us to design an exact (exponential time) algorithm computing -branched treewidth for all ≥ 0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.

is a logic programming language which extends usual clauses by adding intuitionistic implication in goals and clause bodies. This extension can be seen as a form of structuring programs in logic programming. Restricted to the propositional setting of this language, we prove that any goal in can be translated into a monotone Boolean circuit which is linear in the size of the goal.

We show the following results regarding complete sets. These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets.

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is identical. Secondly, we show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if (, ) is a P-separable disjoint NP-pair and (, ) is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs (, ) and (, ) whose degrees lie strictly between (, ) and (, ). Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.

We investigate the complexity of finding prime implicants and minimal equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related problems, the complexity of the monotone case strongly differs from the arbitrary case. We show that it is DP-complete to check whether a monomial is a prime implicant for an arbitrary formula, but checking prime implicants for monotone formulas is in L. We show PP-completeness of checking whether the minimum size of a DNF for a monotone formula is at most . For in unary, we show the complexity of the problem to drop to coNP. In [Uma01] a similar problem for arbitrary formulas was shown to be -complete. We show that calculating the minimal DNF for a monotone formula is possible in output-polynomial time if and only if P = NP. Finally, we disprove a conjecture from [Rei03] by showing that checking whether two formulas are isomorphic has the same complexity for arbitrary formulas as for monotone formulas.

The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are:

In this paper we study the properties of undirected vertex-labeled graphs and the limitations on the languages that they represent. As a main result of this paper we define the necessary and sufficient conditions for the languages to be representable by a class of undirected vertex-labeled graphs and its subclasses. We assume that all obtained results and techniques are transferable to the case of undirected edge-labeled graphs and might give us similar results. The simplicity of necessary conditions emphasizes the naturalness of the result. The proof of their sufficiency is quite non-trivial and it is based on a new notion of quasi-equivalence, that is significantly different from Myhill-Nerode equivalence and might not be reduced to it.

We prove that it is #-hard to compute the mixed discriminant of rank 2 positive semidefinite matrices. We present poly-time algorithms to approximate the ”beast”. We also prove NP-hardness of two problems related to mixed discriminants of rank 2 positive semidefinite matrices. One of them, the so called Full Rank Avoidance problem, had been conjectured to be NP-Complete in [23] and in [25]. We also present a deterministic poly-time algorithm computing the mixed discriminant (,..,) provided that the linear (matrix) subspace generated by {,.., } is small and discuss randomized algorithms approximating mixed discriminants within absolute error.

We introduce and study certain classes of optimization problems over the real numbers. The classes are defined by logical means, relying on metafinite model theory for so called ℝ-structures (see [9],[8]). More precisely, based on a real analogue of Fagin’s theorem [9] we deal with two classes MAX- and MIN- of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX- decomposes into four natural subclasses, whereas MIN- decomposes into two. This gives a real number analogue of a result by Kolaitis and Thakur [10] in the Turing model. Our proofs mainly use techniques from [13]. Finally, approximation issues are briefly discussed.