waashk/dblp huggingface dataset:
succinct ordinal trees with level-ancestor queries. we consider suc cinct or space-efficient representations of trees that efficiently support a variety of navigation operations. we focus on static ordinal trees, i.e., arbitrary static rooted trees where the children of each node are ordered. the set of operations is essentially the union of the sets of operations supported by previous succinct representations (jacobson, proc. 30th focs, 549--554, 1989; munro and raman, siam j. comput. 31 (2001), 762--776; and benoit et. al proc. 6th wads, lncs 1663, 169--180, 1999), to which we add the level-ancestor operation.our representation takes 2n + o(n) bits to represent an n-node tree, which is within o(n) bits of the information-theoretic minimum, and supports all operations in o(1) time on the ram model. these operations also provide a mapping from the n nodes of the tree onto the integers {1,...,n}. in addition to the existing motivations for studying such data structures, we are motivated by the problem of representing xml documents compactly so that xpath queries can be supported efficiently.
computing strongly connected components in a linear number of symbolic steps. we present an algorithm that computes in a linear number of symbolic steps (o(&verbar;v&verbar;)) the strongly connected components (sccs) of a graph g = &lang;v, e&rang; represented by an ordered binary decision diagram (obdd). this result matches the complexity of the (celebrated) tarjan's algorithm operating on explicit data structures. to date, the best algorithm for the above problem works in &theta;(&verbar;v&verbar;log&verbar;v&verbar;) symbolic steps ([bgs00]).
finding dominators revisited: extended abstract. the problem of finding dominators in a flowgraph arises in many kinds of global code optimization and other settings. in 1979 lengauer and tarjan gave an almost-linear-time algorithm to find dominators. in 1985 harel claimed a linear-time algorithm, but this algorithm was incomplete; alstrup et al. [1999] gave a complete and "simpler" linear-time algorithm on a random-access machine. in 1998, buchsbaum et al. claimed a "new, simpler" linear-time algorithm with implementations both on a random access machine and on a pointer machine. in this paper, we begin by noting that the key lemma of buchsbaum et al. does not in fact apply to their algorithm, and their algorithm does not run in linear time. then we provide a complete, correct, simpler linear-time dominators algorithm. one key result is a linear-time reduction of the dominators problem to a nearest common ancestors problem, implementable on either a random-access machine or a pointer machine.
dominator tree verification and vertex-disjoint paths. we present a linear-time algorithm that given a flowgraph g = (v,a,r) and a tree t, checks whether t is the dominator tree of g. also we prove that there exist two spanning trees of g, t1 and t2, such that for any vertex <u>v</u> the paths from r to <u>v</u> in t1 and t2 intersect only at the vertices that dominate <u>v</u>. the proof is constructive and our algorithm can build the two spanning trees in linear time. simpler versions of our two algorithms run in o(m&alpha;(m, n))-time, where n is the number of vertices and m is the number of arcs in g. the existence of such two spanning trees implies that we can order the calculations of the iterative algorithm for finding dominators, proposed by allen and cocke [2], so that it builds the dominator tree in a single iteration.
design of data structures for mergeable trees. motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. this variant allows an operation that merges two tree paths. in contrast to the standard problem, in which only one tree arc at a time changes, a single merge operation can change many arcs. in spite of this, we develop a data structure that supports merges and all other standard tree operations in o(log2 n) amortized time on an n-node forest. for the special case that occurs in the motivating application, in which arbitrary arc deletions are not allowed, we give a data structure with an o(log n) amortized time bound per operation, which is asymptotically optimal. the analysis of both algorithms is not straightforward and requires ideas not previously used in the study of dynamic trees. we explore the design space of algorithms for the problem and also consider lower bounds for it.
random planar graphs with nodes and a fixed number of edges. let p(n, m) be the class of simple labelled planar graphs with n nodes and m edges, and let rn,q be a graph drawn uniformly at random from p(n, [qn]). we show properties that hold with high probability (w.h.p.) for rn,q when 1 < q < 3. for example, we show that rn,q contains w.h.p. linearly many nodes of each given degree and linearly many node disjoint copies of each given fixed connected planar graph. additionally, we show that the probability that rn,q is connected is bounded away from one by a non-zero constant. as a tool we show that (|p(n, [qn])|/n!)1/n tends to a limit as n tends to infinity.
the flow complex: a data structure for geometric modeling. we study a special case of the critical point (morse) theory of distance functions namely, the gradient flow associated with the distance function to a finite point set in r^3. the fixed points of this flow are exactly the critical points of the distance function. our main result is a mathematical characterization and algorithms to compute the stable manifolds, i.e., the inflow regions, of the fixed points. it turns out that the stable manifolds form a polyhedral complex that shares many properties with the delaunay triangulation of the same point set. we call the latter complex the flow complex of the point set. the flow complex is suited for geometric modeling tasks like surface reconstruction.
approximation of functions over redundant dictionaries using coherence. one of the central problems of modern mathematical approximation theory is to approximate functions, or signals, concisely, with elements from a large candidate set called a dictionary. formally, we are given a signal a &isin; rn and a dictionary d = {&phi;i}i&isin;i of unit vectors that span rn. a representation r of b terms for input a &isin; rn is a linear combination of dictionary elements, r = &sigma;i&isin;a &alpha;i&phi;i, for &phi;i &isin; d and some a, &verbar;a&verbar; &ge; b. typically, b ⪡ n, so that r is a concise approximation to signal a. the error of the representation indicates by how well it approximates a, and is given by ∥a - r∥2 = &radic;&sigma;t|a[t - r[t]|2. the problem is to find the best b-term representation, i.e., find a r that minimizes ∥a - r∥2. a dictionary may be redundant in the sense that there is more than one possible exact representation for a, i.e., &verbar;d&verbar; > n = dim(rn). redundant dictionaries are used because, both theoretically and in practice, for important classes of signals, as the size of a dictionary increases, the error and the conciseness of the approximations improve.we present the first known efficient algorithm for finding a provably approximate representation for an input signal over redundant dictionaries. we identify and focus on redundant dictionaries with small coherence (ie., vectors are nearly orthogonal). we present an algorithm that preprocesses any such dictionary in time and space polynomial in &verbar;d&verbar;, and obtains an 1 + &epsilon; approximate representation of the given signal in time nearly linear in signal size n and polylogarithmic in &verbar;d&verbar;; by contrast, most algorithms in the literature require &omega;(&verbar;d&verbar;)time, and, yet, provide no provable bounds. the technical crux of our result is our proof that two commonly used local search techniques, when combined appropriately, gives a provably near-optimal signal representation over redundant dictionaries with small coherence. our result immediately applies to several specific redundant dictionaries considered by the domain experts thus far. in addition, we present new redundant dictionaries which have small coherence (and therefore are amenable to our algorithms) and yet have significantly large sizes, thereby adding to the redundant dictionary construction literature.work with redundant dictionaries forms the emerging field of highly nonlinear approximation theory. we have presented algorithmic results for some of the most basic problems in this area, but other mathematical and algorithmic questions remain to be explored.
correlation clustering with a fixed number of clusters. we continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied recently [5, 7, 8, 3]. the basic setup here is that we are given as input a complete graph on n nodes (which correspond to nodes to be clustered) whose edges are labeled + (for similar pairs of items) and - (for dissimilar pairs of items). thus we have only as input qualitative information on similarity and no quantitative distance measure between items. the quality of a clustering is measured in terms of its number of agreements, which is simply the number of edges it correctly classifies, that is the sum of number of - edges whose endpoints it places in different clusters plus the number of + edges both of whose endpoints it places within the same cluster.in this paper, we study the problem of finding clusterings that maximize the number of agreements, and the complementary minimization version where we seek clusterings that minimize the number of disagreements. we focus on the situation when the number of clusters is stipulated to be a small constant k. our main result is that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements. (the problems are np-hard for every k &ge; 2.) the main technical work is for the minimization version, as the ptas for maximizing agreements follows along the lines of the property tester for max k-cut from [13].in contrast, when the number of clusters is not specified, the problem of minimizing disagreements was shown to be apx-hard [7], even though the maximization version admits a ptas.
stability of networks and protocols in the adversarial queueing model for packet routing. the adversarial queueing theory model for packet routing was suggested by borodin et al. we give a complete and simple characterization of all networks that are universally stable in this model. we show that a specific greedy protocol, sis (shortest in system), is stable against a large class of stochastic adversaries. new applications such as multicast packet scheduling and job scheduling with precedence constraints xsare suggested for the adversarial model.
simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. we consider the problem of finding efficient trees to send information from k sources to a single sink in a network where information can be aggregated at intermediate nodes in the tree. specifically, we assume that if information from j sources is traveling over a link, the total information that needs to be transmitted is f(j). one natural and important (though not necessarily comprehensive) class of functions is those which are concave, non-decreasing, and satisfy f(0) = 0. our goal is to find a tree which is a good approximation simultaneously to the optimum trees for all such functions. this problem is motivated by aggregation in sensor networks, as well as by buy-at-bulk network design.we present a randomized tree construction algorithm that guarantees e[maxfcf/c*(f)] 1 + log k, where cf is a random variable denoting the cost of the tree for function f and c* (f) is the cost of the optimum tree for function f. to the best of our knowledge, this is the first result regarding simultaneous optimization for concave costs. we also show how to derandomize this result to obtain a deterministic algorithm that guarantees maxf/c*(f) = o(log k). both these results are much stronger than merely obtaining a guarantee on maxfe[cf/c* (f)]. a guarantee on maxfe[cf/c* (f)] can be obtained using existing techniques, but this does not capture simultaneous optimization since no one tree is guaranteed to be a good approximation for all f simultaneously.while our analysis is quite involved, the algorithm itself is very simple and may well find practical use. we also hope that our techniques will prove useful for other problems where one needs simultaneous optimization for concave costs.
online throughput-competitive algorithm for multicast routing and admission control. we present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. the ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is polylogarithmic in m and n, where m is the number of multicast groups and n is the number of nodes in the graph. we show that this is close to optimum by presenting an omega(log n log m) lower bound on this ratio for any randomized online algorithm against an oblivious adversary. we also show that it is impossible to be competitive against an adaptive online adversary. as in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. in contrast to the previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. the new new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.
reductions among high dimensional proximity problems. we present improved running times for a wide range of approximate high dimensional proximity problems. we obtain subquadratic running time for each of these problems. these improved running times are obtained by reduction to nearest neighbour queries. the problems we consider in this paper are approximate diameter, approximate furthest neighbours, approximate discrete center, approximate metric facility location, approximate bottleneck matching, and approximate minimum weight matching.
approximate majorization and fair online load balancing. this article relates the notion of fairness in online routing and load balancing to vector majorization as developed by hardy et al. [1929]. we define &alpha;-supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by kleinberg et al. [2001] as well as the popular notion of max-min fairness.the article revisits the problem of online load-balancing for unrelated 1-&infin; machines from the viewpoint of fairness. we prove that a greedy approach is o(log n)-supermajorized by all other allocations, where n is the number of jobs. this means the greedy approach is globally o(log n)-fair. this may be contrasted with polynomial lower bounds presented by goel et al. [2001] for fair online routing.we also define a machine-centric view of fairness using the related concept of submajorization. we prove that the greedy online algorithm is globally o(log m)-balanced, where m is the number of machines.
distributed admission control, scheduling, and routing with stale information. we study the problem of distributed online admission control and routing of permanent virtual circuits in a capacitated network. we assume that we have k distinct decision makers, each of which is responsible for gathering its own information about the state of the network. through simulation, we demonstrate that an exponential based routing scheme will perform well in a distributed model provided granularity is sufficiently high. in order to ground these results theoretically, we prove that exponential-based schemes attain best-possible competitive ratios (same as for the centralized case) provided each edge can accommodate at least &ohgr;(k log n) requests. a matching lower-bound shows that no deterministic algorithm can attain best-possible competitive ratios without requiring the same level of granularity. in the randomized case, we present a modified exponential-based approach which obtains best-possible competitive ratios provided the granularity is at least &ohgr;(k + log n). our results may be extended to the case where different requests have different profits, and where requests are allowed to be temporary. they also apply to admission control and scheduling for unrelated machines.
cooperative facility location games. the location of facilities in order to provide service for customers is a well-studied problem in the operations research literature. in the basic model, there is a predefined cost for opening a facility and also for connecting a customer to a facility, the goal being to minimize the total cost. often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations,....) and private facilities (such as distribution centers, switching stations, ....), we may want to find a 'fair' allocation of the total cost to the customers-this is known as the cost allocation problem. a central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them. we establish strong connections between fair cost allocations and linear programming relaxations for several variants of the facility location problem. in particular, we show that a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation; this was only known for the simplest unconstrained variant of the facility location problem. moreover, we introduce a subtle variant of randomized rounding and derive new proofs for the existence of fair cost allocations for several classes of instances. we also show that it is in general np-complete to decide whether a fair cost allocation exists and whether a given allocation is fair.
covering minimum spanning trees of random subgraphs. we consider the problem of covering the minimum spanning tree (mst) of a random subgraph of g by a sparse set of edges, with high probability. the two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p.let n be the number of vertices in g. we show that in both cases, there is a covering set q of cardinality o(n logb n) where b = 1/(1 -- p) (and p is possibly a function of n) and this is asymptotically optimal. more generally, we show a similar bound on the covering set in a matroid, which contains the minimum-weight basis of a random subset with high probability. also, we give a randomized algorithm which calls an mst subroutine only a polylogarithmic number of times, and finds the covering set with high probability.
a general approximation technique for constrained forest problems. we present a general approximation technique for a large class of graph problems. our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. in particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman and steiner tree problems. our technique produces approximation algorithms that run in o(n2 log n) time and come within a factor of 2 of optimal for most of these problems. for instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. our running time of o(n2 log n) time compares favorably with the best strongly polynomial exact algorithms running in o(n3) time for dense graphs. a similar result is obtained for the 2-matching problem and its variants.we also derive the first approximation algorithms for many np-complete problems, including the non-fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. moreover, for the prize-collecting traveling salesman or steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [4].
two-dimensional gantt charts and a scheduling algorithm of lawler. in this note we give an alternate proof that a scheduling algorithm of lawler [e. l. lawler, ann. discrete math., 2 (1978), pp. 75--90, e. l. lawler and j. k. lenstra, in ordered sets, i. rival, ed., d. reidel, 1982, pp. 655--675] finds the optimal solution for the scheduling problem $1 | prec | \sum_j w_j c_j$ when the precedence constraints are series-parallel. we do this by using a linear programming formulation of $1 | prec | \sum_j w_j c_j$ introduced by queyranne and wang. [ math. oper. res., 16 (1991), pp. 1--20]. queyranne and wang proved that their formulation completely describes the scheduling polyhedron in the case of series-parallel constraints; a by-product of our proof of correctness of lawler's algorithm is an alternate proof of this fact. in the course of our proof it is helpful to use what might be called two-dimensional (2d) gantt charts. we think these may find independent use, and to illustrate this we show that some recent work in the area becomes transparent using 2d gantt charts.
scaling algorithms for the shortest paths problem. we describe a new method for designing scaling algorithms for the single-source shortest paths problem and use this method to obtain an $o(\sqrt n m \log n)$ algorithm for the problem. (here $n$ and $m$ is the number of nodes and arcs in the input network and $n$ is essentially the absolute value of the most negative arc length, and arc lengths are assumed to be integral.) this improves previous bounds for the problem. the method extends to related problems.
competitiveness via consensus. we introduce the following consensus estimate problem. several processors hold private and possibly different lower bounds on a value. the processors do not communicate with each other, but can observe a shared source of random numbers. the goal is to come up with a consensus lower bound on the value that is as high as possible. we give a solution to the consensus estimate problem and show how it is useful in the context of mechanism design. the consensus problem is natural and may have other applications. based on our consensus estimate technique, we introduce consensus revenue estimate (core) auctions. this is a class of competitive revenue-maximizing auctions that is interesting for several reasons. one auction from this class achieves a better competitive ratio than any previously known auction. another one uses only two random bits, whereas the previously known competitive auctions on n bidders use n random bits. furthermore, a parameterized core auction performs better than the previous auctions in the context of mass-market goods, such as digital goods.
computing the shortest path: search meets graph theory. we propose shortest path algorithms that use a* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. our algorithms compute optimal shortest paths and work on any directed graph. we give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular a* search with euclidean bounds, by a wide margin on road networks and on some synthetic problem families.