Catálogo de publicaciones - libros

We show that whenever there is a sharp drop in the numerical rank defined by a personalized PageRank vector, the location of the drop reveals a cut with small conductance. We then show that for any cut in the graph, and for many starting vertices within that cut, an approximate personalized PageRank vector will have a sharp drop sufficient to produce a cut with conductance nearly as small as the original cut. Using this technique, we produce a nearly linear time local partitioning algorithm whose analysis is simpler than previous algorithms.

The compactness theorem and Gödel’s completeness theorem are perhaps the most important tools of mathematical logic for creating extensions of an existing model of a given theory. Unfortunately none of these theorems hold if we restrict our attention to finite models. In this paper we give generalizations of these theorems which can be used to construct extensions of nonstandard versions of finite structures. Therefore, although the structures are infinite, some finiteness properties will be true both for the original and the extended structures. These types of model extensions are closely related to questions in complexity theory.

We study non-overlapping axis-parallel packings of 3D boxes with profits into a dedicated bigger box where rotation is forbidden; we wish to maximize the total profit. Since this optimization problem is NP-hard, we focus on approximation algorithms. We obtain fast and simple algorithms with approximation ratios 9 +  and 8 +  as well as an algorithm with approximation ratio 7 +  that uses more sophisticated techniques; these are the smallest approximation ratios known for this problem. Algorithms, computational and structural complexity.

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of distinct numbers into minimum number of monotone (increasing or decreasing) subsequences. This problem is NP-hard and the number of monotone subsequences can reach in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than monotone subsequences in () time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity (), a known greedy algorithm of time complexity (log), and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant times of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.

In this paper, motivated by the work of Azar et al. [3] we consider selective network design on bottleneck routing games. Assuming ≠ we achieve the following results. For the the trivial algorithm is a best possible approximation algorithm. For the it is -hard to compute a best . Moreover no polynomial time algorithms can have a constant approximation ratio if the edge latency functions are continuous and non-decreasing.

A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.

It is shown that Th() ≠ Th () holds for every  > 1, where is the upper semi-lattice of all high computably enumerable (c.e.) degrees for  > 0, giving a first elementary difference among the highness hierarchies of the c.e. degrees.

We say that  ≤  if every -random number is -random. Intuitively this means that if oracle can identify some patterns on some real , oracle can also find patterns on . In other words, is at least as good as for this purpose. We propose a methodology for studying the degrees and present a number of recent results of ours, including sketches of their proofs.

In this paper we investigate aspects of effectivity and computability on closed and compact subsets of locally compact spaces. We use the framework of the representation approach, TTE, where continuity and computability on finite and infinite sequences of symbols are defined canonically and transferred to abstract sets by means of notations and representations. This work is a generalization of the concepts introduced in [4] and [22] for the Euclidean case and in [3] for metric spaces. Whenever reasonable, we transfer a representation of the set of closed or compact subsets to locally compact spaces and discuss its properties and their relations to each other.

Distance-hereditary graphs consist of the isometric graphs, and hence contain trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time using two prefix trees. Usually, the prefix trees are used to maintain a set of strings. The prefix trees in our algorithm are used to maintain the neighbors for each vertex, which is new approach comparing to the other known results based on the lexicographically bread first search. Several efficient algorithms for the distance-hereditary graphs based on the canonical tree representation are proposed; linear time algorithms for graph recognition and graph isomorphism, and efficient enumeration algorithm. An efficient coding for the tree representation is also presented, which requires 4 bits for a distance-hereditary graph of vertices, and 3 bits for a cograph. The results improve previously known upper bounds of the number of distance-hereditary graphs and cographs.