waashk/dblp huggingface dataset:
authoritative sources in a hyperlinked environment. the network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. we develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the world wide web. the central issue we address within our framework is the distillation of broad search topics, through the discovery of &ldquo;authorative&rdquo; information sources on such topics. we propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of &ldquo;hub pages&rdquo; that join them together in the link structure. our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
on binary searching with non-uniform costs. let us consider an ordered vector a[1 : n]. if the cost of testing each position is similar, then the standard binary search is the best strategy to search the vector. this is true in both average and worst case. however, if the costs are non-uniform, then the best strategy is not necessarily the standard binary search. the best algorithm to construct a strategy that minimizes the expected search cost runs in &ogr;(n3) time and requires &ogr;(n2) space. the same complexities hold for the best algorithm to construct a strategy that minimizes the worst case search cost. here, we show how to efficiently construct search strategies that are at most at a constant factor from the optimal one. these constructions take linear time and use only linear space. for the problem of minimizing the expected search cost, we present an algorithm that requires &ogr;(n) space and gives a (2 + &isin; + &ogr;(1))-approximated solution in &ogr;(n) time, for any fixed value of &isin; > 0. on the other hand, for the problem of minimizing the worst case search cost, we describe an algorithm that requires &ogr;(n) space and gives a (2 + &isin; + &ogr;(1))- approximated solution in &ogr;(n) time, for any fixed value of &isin; > 0. these two problems arise when processing a query in a distributed text database indexed by a suffix array.
isomorphism and embedding problems for infinite limits of scale-free graphs. the study of random graphs has traditionally been dominated by the closely-related models g(n, m), in which a graph is sampled from the uniform distribution on graphs with n vertices and m edges, and g(n, p), in which each of the (n/2) edges is sampled independently with probability p. recently, however, there has been considerable interest in alternate random graph models designed to more closely approximate the properties of complex real-world networks such as the web graph, the internet, and large social networks. two of the most well-studied of these are the closely related "preferential attachment" and "copying" models, in which vertices arrive one-by-one in sequence and attach at random in "rich-get-richer" fashion to d earlier vertices.here we study the infinite limits of the preferential attachment process --- namely, the asymptotic behavior of finite graphs produced by preferential attachment (brie y, pa graphs), as well as the infinite graphs obtained by continuing the process indefinitely. we are guided in part by a striking result of erd&ouml;;s and r&eacute;nyi on countable graphs produced by the infinite analogue of the g(n, p) model, showing that any two graphs produced by this model are isomorphic with probability 1; it is natural to ask whether a comparable result holds for the preferential attachment process.we find, somewhat surprisingly, that the answer depends critically on the out-degree d of the model. for d = 1 and d = 2, there exist infinite graphs r&infin;d such that a random graph generated according to the infinite preferential attachment process is isomorphic to r&infin;d with probability 1. for d &ge; 3, on the other hand, two different samples generated from the infinite preferential attachment process are non-isomorphic with positive probability. the main technical ingredients underlying this result have fundamental implications for the structure of finite pa graphs; in particular, we give a characterization of the graphs h for which the expected number of subgraph embeddings of h in an n-node pa graph remains bounded as n goes to infinity.
computation in noisy radio networks. in this paper, we examine noisy radio (broadcast) networks in which every bit transmitted has a certain probability of being flipped. each processor has some initial input bit, and the goal is to compute a function of these input bits. in this model, we show a protocol to compute any threshold function using only a linear number of transmissions.
wavelength conversion in optical networks. in many models of optical routing, we are given a set of communication paths in a network, and we must assign a wavelength to each path so that paths sharing an edge receive different wavelengths. the goal is to assign as few wavelengths as possible, in order to make as efficient use as possible of the optical bandwidth. wilfong and winkler considered the problem of placing wavelength converters in such a network: if a node of the network contains a converter, any path that passes through this node may change its wavelength. having converters at some of the nodes can reduce the number of wavelengths required for routing, down to the following natural {\em congestion bound}: even with converters, we will always need at least as many wavelengths as the maximum number of paths sharing a single edge. thus winkler and wilfong defined a set $s$ of nodes in a network to be {\em sufficient} if, placing converters at the nodes in $s$, every set of paths can be routed with a number of wavelengths equal to its congestion bound. they showed that finding a sufficient set of minimum size is np-complete. in this paper, we provide a polynomial-time algorithm to find a sufficient set for an arbitrary directed network whose size is within a factor of $2$ of minimum. for the special case of planar graphs with bi-directional edges, we obtain a polynomial-time approximation scheme. our techniques establish a connection between the problem of finding a minimum sufficient set and an interesting simultaneous generalization of the vertex cover and feedback vertex set problems in undirected graphs.
network failure detection and graph connectivity. we consider a model for monitoring the connectivity of a network subject to node or edge failures. in particular, we are concerned with detecting (ε, k)-failures: events in which an adversary deletes up to network elements (nodes or edges), after which there are two sets of nodes a and b, each at least an ε fraction of the network, that are disconnected from one another. we say that a set d of nodes is an (ε k)-detection set if, for any (ε k)-failure of the network, some two nodes in d are no longer able to communicate; in this way, d "witnesses" any such failure. recent results show that for any graph g, there is an is (ε k)-detection set of size bounded by a polynomial in k and ε, independent of the size of g.in this paper, we expose some relationships between bounds on detection sets and the edge-connectivity &lambda; and node-connectivity &kappa; of the underlying graph. specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. we show that for an adversary that can delete &kappa;&lambda; edges, there is always a detection set of size o((&kappa;/ε) log (1/ε)) which can be found by random sampling. moreover, an (ε, &lambda)-detection set of minimum size (which is at most 1/ε) can be computed in polynomial time. a crucial point is that these bounds are independent not just of the size of g but also of the value of &lambda;.extending these bounds to node failures is much more challenging. the most technically difficult result of this paper is that a random sample of o((&kappa;/ε) log (1/ε)) nodes is a detection set for adversaries that can delete a number of nodes up to &kappa;, the node-connectivity.for the case of edge-failures we use vc-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph.
adaptive heuristics for binary search trees and constant linkage cost. we present lower and upper bounds on adaptive heuristics for maintaining binary search trees using a constant number of link or pointer changes for each operation (constant linkage cost (clc)). we show that no adaptive heuristic with an amortized linkage cost of o(log n) can be competitive. in particular, we show that any heuristic that performs f(n)=o(log n) promotions (rotations) amortized over each access has a competitive ratio of at least $\omega(\log n/f(n))$ against an oblivious adversary, and any heuristic that performs f(n)=o(log n) pointer changes amortized over each access has a competitive ratio of at least $\omega(\frac{\log n}{f(n)\log(\log n/f(n))})$ against an adaptive online adversary.in our investigation of upper bounds we present four adaptive heuristics: a randomized, worst-case-clc heuristic randomized two-promotion (r2p) whose expected search time is within a constant factor of the search time using an optimal tree; that is, it is statically competitive against an oblivious adversary; a randomized, expected-clc heuristic (locally optimized randomized partial splay (lorps)) that has o(log n) expected-amortized update time and is statically competitive against an oblivious adversary; a deterministic, amortized-clc heuristic (locally optimized partial splay (lops)) that has o(log n) amortized update time and is statically competitive against an adaptive adversary; a practical, randomized heuristic (randomized partial splay (rps)) that is not clc but has performance bounds comparable with those of the splay heuristic of sleator and tarjan; it is statically competitive against an adaptive adversary. the randomized heuristics use only constant extra space, whereas the deterministic heuristic uses o(n) extra space.
performance guarentee for online deadline scheduling in the presence of overload. earliest deadline first (edf) is a widely-used online algorithm for scheduling jobs with deadlines in real-time systems. yet, existing results on the performance guarantee of edf are limited to underloaded systems [6,12,14]. this paper initiates the study of edf for overloaded systems, attaining similar performance guarantees as in the underloaded setting. specifically, we show that edf with a simple form of admission control is optimal for scheduling on both uniprocessor and multiprocessors when moderately faster processors are available (our analysis actually admits a tradeoff between speed and extra processors). this is the first result attaining optimality under overload. another contribution of this paper is an improved analysis of the competitiveness for weighted deadline scheduling.
polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). we consider three graph partitioning problems, both from the vertices and the edges point of view. these problems are dominating set, list-q-coloring with costs (fixed number of colors q) and coloring with non-fixed number of colors. they are all known to be np-hard in general. we show that all these problems (except edge-coloring) can be solved in polynomial time on graphs with clique-width bounded by some constant k, if the k-expression of the input graph is also given. in particular, we present the first polynomial algorithms (on these classes) for chromatic number, edge-dominating set and list-q-coloring with costs (fixed number of colors q, both vertex and edge versions). since these classes of graphs include classes like p4-sparse graphs, distance hereditary graphs and graphs with bounded treewidth, our algorithms also apply to these graphs.
girth restrictions for the 5-flow conjecture. using counting arguments, we show that every smallest counterexample to tutte's 5-flow conjecture (that every bridgeless graph has a nowhere-zero 5-flow) has girth at least nine.
distinguishing string selection problems. this paper presents a collection of string algorithms that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, universal primers or unbiased consensus sequences. all these problems reduce to the task of finding a pattern that, with some error, occurs in one set of strings (closest substring problem) and does not occur in another set (farthest string problem). in this paper, we break down the problem into several subproblems and prove the following results. 1. the following are all np-hard: the farthest string problem, the closest substring problem, and the closest string problem of finding a string that is close to each string in a set. 2. there is a ptas for the farthest string problem based on a linear programming relaxation technique. 3. there is a polynomial-time (4/3 + ε)-approximation algorithm for the closest string problem for any small constant ε > 0. using this algorithm, we also provide an efficient heuristic algorithm for the closest substring problem. 4. the problem of finding a string that is at least hamming distance d from as many strings in a set as possible, cannot be approximated within nε in polynomial time for some fixed constant ε unless np = p, where n is the number of strings in the set. 5. there is a polynomial-time 2-approximation for finding a string that is both the closest substring to one set, and the farthest string from another set.
a near-tight approximation lower bound and algorithm for the kidnapped robot problem. localization is a fundamental problem in robotics. the 'kidnapped robot' possesses a compass and map of its environment; it must determine its location at a minimum cost of travel distance. the problem is np-hard [6] even to minimize within factor c log n[21], where n is the number of vertices. no approximation algorithm has been known. we give a o(log3 n)-factor algorithm. the key idea is to plan travel in a 'majority-rule' map, which eliminates uncertainty and permits a link to the 1/2-group steiner (not group steiner) problem. the approximation factor is not far from optimal: we prove a c log2-&epsilon; n lower bound, assuming np &nsube; ztime(npolylog(n)), for the grid graphs commonly used in practice. we also introduce a new hypothesis equivalence decomposition of the plane, built from pairs of aspect graph duals, in order to extend the algorithm to polygonal maps.
navigating nets: simple algorithms for proximity search. we present a simple deterministic data structure for maintaining a set s of points in a general metric space, while supporting proximity search (nearest neighbor and range queries) and updates to s (insertions and deletions). our data structure consists of a sequence of progressively finer ε-nets of s, with pointers that allow us to navigate easily from one scale to the next.we analyze the worst-case complexity of this data structure in terms of the "abstract dimensionality" of the metric s. our data structure is extremely efficient for metrics of bounded dimension and is essentially optimal in a certain model of distance computation. finally, as a special case, our approach improves over one recently devised by karger and ruhl [kr02].
an optimal algorithm for checking regularity (extended abstract). we present a deterministic algorithm a that, in o(m2) time, verifies whether a given m by m bipartite graph g is regular, in the sense of szemer&eacute;di [18]. in the case in which g is not regular enough, our algorithm outputs a witness to this irregularity. algorithm a may be used as a subroutine in an algorithm that finds an &epsilon;-regular partition of a given n-vertex graph &gamma; in time o(n2). this time complexity is optimal, up to a constant factor, and improves upon the bound o(m(n)), proved by alon, duke, lefmann, r&ouml;dl, and yuster [1, 2], where m(n) = o(n2.376) is the time required to square a 0-1 matrix over the integers.our approach is elementary, except that it makes use of linear-sized expanders to accomplish a suitable form of deterministic sampling.
pattern matching in a digitized image. the continuous pattern matching problem is defined. given are two pictures, each consisting of unicolor regions; one picture is called the scene and the other the pattern. the problem is to find all occurrences of the pattern in the scene. as a step towards efficient algorithmic handling of the continuous pattern matching problem by computers, where discretized representations are involved, we give several algorithms. our strongest algorithmic result is for a one-dimensional version of the problem, where running time which is linear in the length of a digitized representation is achieved. the definitions of our problems are derived from a &ldquo;digitized-based&rdquo; approach to object recognition problems in computer vision, which is different from a common computer vision approach. the digitized based approach may lead towards further research within the discrete algorithms community on computer vision problems.
flows over time with load-dependent transit times. more than forty years ago, ford and fulkerson studied maximum s-t-flows over time (also called "dynamic" flows) in networks with fixed transit times on the arcs and a fixed time horizon. here, flow on arcs may change over time and transit times specify the amount of time it takes for flow to travel through a particular arc. ford and fulkerson proved that there always exists an optimal solution which sends flow on certain s-t-paths at a constant rate as long as there is enough time left for the flow along a path to arrive at the sink; a flow over time featuring this simple structure is called "temporally repeated."although this result does not hold for the more general and also more realistic setting where transit times depend on the current flow situation, we show that there always exists a provably good temporally repeated solution. moreover, such a solution can be determined very efficiently by only one minimum convex cost flow computation. our results rest upon a new model of flow-dependent transit times. it is based on two assumption on the pace of flow on a particular arc. first, the pace of flow on an arc is assumed to be uniform for all flow units on an arc for each point in time. second, this uniform pace is for each moment determined by the actual amount of flow on this arc. finally, we show that the resulting flow-over-time problem is strongly np-hard and cannot be approximated with arbitrary precision in polynomial time, unless p=np.
a new approach to proving upper bounds for max-2-sat. in this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (max-2-sat). we present a new 2k/5.5-time algorithm for max-2-sat, where k is the number of clauses in an input formula. we also obtain a 2n/6 bound, where n is the number of variables in an input formula, for a particular case of max-2-sat, where each variable appears in at most three 2-clauses. this immediately implies a 2n/6 bound, where n is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. the key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. by using a new complexity measure we are able to provide a much simpler proof of new upper bounds for max-2-sat than proofs of previously known bounds.
provably good moving least squares. we analyze a moving least squares (mls) interpolation scheme for reconstructing a surface from point cloud data. the input is a sufficiently dense set of sample points that lie near a closed surface f with approximate surface normals. the output is a reconstructed surface passing near the sample points. for each sample point s in the input, we define a linear point function that represents the local shape of the surface near s. these point functions are combined by a weighted average, yielding a three-dimensional function i. the reconstructed surface is implicitly defined as the zero set of i. we prove that the function i is a good approximation to the signed distance function of the sampled surface f and that the reconstructed surface is geometrically close to and isotopic to f. our sampling requirements are derived from the local feature size function used in delaunay-based surface reconstruction algorithms. our analysis can handle noisy data provided the amount of noise in the input dataset is small compared to the feature size of f.
improved bounds for the unsplittable flow problem. in this paper we consider the unsplittable flow problem (ufp): given a directed or undirected network g=(v,e) with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. we present a collection of new results for the ufp both in the offline (all requests are given from the beginning) and the online (requests arrive at the system one after the other) setting. a fundamental ingredient of our analysis is the introduction of a new graph parameter, the flow number, that aims to capture global communication properties of the network. with the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only. this generalizes a well-known theorem of leighton and rao [j. acm 46 (6) (1999) 787-832] that applies to uniform flows only. both the parameter and the method may therefore be of independent interest.
improved lower bounds for embeddings into . we simplify and improve upon recent lower bounds on the minimum distortion of embedding certain finite metric spaces into l1. in particular, we show that for infinitely many values of n there are n-point metric spaces of negative type that require a distortion of &omega;(log log n) for such an embedding, implying the same lower bound on the integrality gap of a well-known sdp relaxation for sparsest-cut. this result builds upon and improves the recent lower bound of (log log n)1/6---o(1) due to khot and vishnoi [stoc 2005]. we also show that embedding the edit distance on {o, 1}n into l1 requires a distortion of &omega;(log n). this result simplifies and improves a very recent lower bound due to khot and naor [focs 2005].
pianos are not flat: rigid motion planning in three dimensions. consider a robot r that is either a line segment or the minkowski sum of a line segment and a 3-ball, and a set s of polyhedral obstacles with a total of n vertices in r3. we design near-optimal exact algorithms for planning the motion of r among s when r is allowed to translate and rotate. specifically, we can preprocess s in time o(n 4+&epsilon;) for any &epsilon; > 0 into a data structure that given two placements &alpha; and &beta; of r, can decide in time o(log n) whether a collision-free rigid motion of r between &alpha; and &beta; exists and if so, output such a motion in time asymptotically proportional to its complexity. furthermore, we can find in time o(n4+&epsilon;) for any &epsilon; > 0 the largest placement of a similar (translated, rotated and scaled) copy of r that does not intersect s. a number of additional stronger results are provided. our line segment motion planning algorithm improves the result of ke and o'rourke by two orders of magnitude and almost matches their lower bound, thus settling a classical motion planning problem first considered by schwartz and sharir in 1984. this implies a number of natural directions for future work concerning rigid motion planning in three dimensions.