waashk/dblp huggingface dataset:
optimal constrained graph exploration. we address the problem of constrained exploration of an unknown graph g &equals; (v, e) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. in both variations of the problem, the robot can only move along the edges of the graph, for example, it cannot jump between nonadjacent nodes. in the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. in the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing c edges. the efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. we present an algorithm for a tethered robot that explores the graph in &theta;(&verbar;e&verbar;) edge traversals. the problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &theta;(&verbar;e&verbar;) algorithm. this improves on the previous best-known bound of o(&verbar;e&verbar; &plus; &verbar;v&verbar;log2&verbar;v&verbar;). since the lower bound for the graph exploration problems is &ohm;(&verbar;e&verbar;), our algorithm is optimal within a constant factor.
rank-maximal matchings. suppose that each member of a set a of applicants ranks a subset of a set p of posts in an order of preference, possibly involving ties. a matching is a set of (applicant, post) pairs such that each applicant and each post appears in at most one pair. a rank-maximal matching is one in which the maximum possible number of applicants are matched to their first choice post, and subject to that condition, the maximum possible number are matched to their second choice post, and so on. this is a relevant concept in any practical matching situation and it was first studied by irving [2003].we give an algorithm to compute a rank-maximal matching with running time o(min(n &plus; c,c &sqrt;n)m), where c is the maximal rank of an edge used in a rank-maximal matching, n is the number of applicants and posts and m is the total size of the preference lists.
a loopless gray code for rooted trees. beyer and hedetniemi [1980] gave the first constant average-time algorithm for the generation of all rooted trees with n nodes. this article presents the first combinatorial gray code for these trees and a loopless algorithm for its generation.
generating rooted and free plane trees. this article has two main results. first, we develop a simple algorithm to list all nonisomorphic rooted plane trees in lexicographic order using a level sequence representation. then, by selecting a unique centroid to act as the root of a free plane tree, we apply the rooted plane tree algorithm to develop an algorithm to list all nonisomorphic free plane trees. the latter algorithm also uses a level sequence representation and lists all free plane trees with a unique centroid first followed by all free plane trees with two centroids. both algorithms are proved to run in constant amortized time using straightforward bounding methods.
pattern matching for arc-annotated sequences. we study pattern matching for arc-annotated sequences. an o(nm) time algorithm is given for the problem to determine whether a length m sequence with nested arc annotation is an arc-preserving subsequence (aps) of a length n sequence with nested arc annotation, called aps(nested,nested). arc-annotated sequences and, in particular, those with nested arc annotation are motivated by applications in rna structure comparison. our algorithm generalizes results for ordered tree inclusion problems and it is useful for recent fixed-parameter algorithms for lapcs(nested,nested), which is the problem of computing a longest arc-preserving common subsequence of two sequences with nested arc annotations. in particular, the presented dynamic programming methodology implies a quadratic-time algorithm for an open problem posed by vialette.
melding priority queues. we show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. more specifically, the new data structure supports insert, meld and find-min operations in o(1) amortized time, and delete operations in o(pq(n) &plus; &alpha;(n)) amortized time, where &alpha;(n) is a functional inverse of the ackermann function, and where n this time is the total number of operations performed on all the priority queues. the construction is very simple. the meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. we also show that when all keys are integers in the range [1, n], we can replace n in the bound stated previously by min&lcub;n, n&rcub;.applying this result to the nonmeldable priority queue data structures obtained recently by thorup [2002b] and by han and thorup [2002] we obtain meldable ram priority queues with o(log log n) amortized time per operation, or o(&sqrt;log log n) expected amortized time per operation, respectively. as a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic o(m log log n)-time algorithm and a randomized o(m&sqrt;log log n)-time algorithm. for sparse enough graphs, these bounds improve on the o(m &plus; n log n) running time of an algorithm by gabow et al. [1986] that works for arbitrary edge weights.
a general approach to online network optimization problems. we study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. in a general online network design problem, we have a communication network known to the algorithm in advance. what is not known in advance are the connectivity (bandwidth) or cut demands between vertices in the network which arrive online.we develop a unified framework for designing online algorithms for problems involving connectivity and cuts. we first present a general o(log m)-competitive deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph. this may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to both directed and undirected graphs. we then show how to obtain integral solutions via an online rounding of the fractional solution. this part of the framework is problem dependent, and applies various tools including results on approximate max-flow min-cut for multicommodity flow, the hierarchically separated trees (hst) method and its extensions, certain rounding techniques for dependent variables, and r&auml;cke's new hierarchical decomposition of graphs.specifically, our results for the integral case include an o(log mlog n)-competitive randomized algorithm for the online nonmetric facility location problem and for a generalization of the problem called the multicast problem. in the nonmetric facility location problem, m is the number of facilities and n is the number of clients. the competitive ratio is nearly tight. we also present an o(log2nlog k)-competitive randomized algorithm for the online group steiner problem in trees and an o(log3nlog k)-competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. finally, we design a deterministic o(log3nlog log n)-competitive algorithm for the online multi-cut problem.
an improved algorithm for radio broadcast. we show that for every radio network g &equals; (v, e) and source s &isin; v, there exists a radio broadcast schedule for g of length rad(g, s) &plus; o(&sqrt;rad(g, s) &sdot;log2 n) &equals; o(rad(g, s) &plus; log4 n), where rad(g, s) is the radius of the radio network g with respect to the source s. this result improves the previously best-known upper bound of o(rad(g, s) &plus; log5 n) due to gaber and mansour [1995]. for graphs with small genus, particularly for planar graphs, we provide an even better upper bound of rad(g, s) &plus; o(&sqrt;rad(g,s) &sdot; log n &plus; log3 n) &equals; o(rad(g, s) &plus; log3 n).
on the difficulty of some shortest path problems. we prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. the central problem in our study is the replacement paths problem: given a directed graph g with non-negative edge weights, and a shortest path p &equals; &lcub;e1, e2, &hellip;, ep&rcub; between two nodes s and t, compute the shortest path distances from s to t in each of the p graphs obtained from g by deleting one of the edges ei. we show that the replacement paths problem requires &omega;(m &sqrt;n) time in the worst case whenever m &equals; o(n &sqrt;n). our construction also implies a similar lower bound on the k shortest simple paths problem for a broad class of algorithms that includes all known algorithms for the problem. to put our lower bound in perspective, we note that both these problems (replacement paths and k shortest simple paths) can be solved in near-linear time for undirected graphs.
querying priced information in databases: the conjunctive case. query optimization that involves expensive predicates has received considerable attention in the database community. typically, the output to a database query is a set of tuples that satisfy certain conditions, and, with expensive predicates, these conditions may be computationally costly to verify. in the simplest case, when the query looks for the set of tuples that simultaneously satisfy k expensive predicates, the problem reduces to ordering the evaluation of the predicates so as to minimize the time to output the set of tuples comprising the answer to the query. we study different cases of the problem: the sequential case, in which a single processor is available to evaluate the predicates, and the distributed case, in which there are k processors available, each dedicated to a different attribute (column) of the database, and there is no communication cost between the processors. for the sequential case, we give a simple and fast deterministic k-approximation algorithm, and prove that k is the best possible approximation ratio for a deterministic algorithm, even if exponential time algorithms are allowed. we also propose a randomized, polynomial time algorithm with expected approximation ratio 1 &plus; &sqrt;2/2 &ap; 1.707 for k &equals; 2, and prove that 3/2 is the best possible expected approximation ratio for randomized algorithms. we also show that given 0 &le; &epsiv; &le; 1, no randomized algorithm achieves approximation ratio smaller than 1 &plus; &epsiv; with probability larger than (1 &plus; &epsiv;)/2. for the distributed case, we consider two different models: the preemptive model, in which a processor is allowed to interrupt the evaluation of a predicate, and the nonpreemptive model, in which the evaluation of a predicate must be completed once started. we show that k is the best possible approximation ratio for a deterministic algorithm, even if exponential time algorithms are allowed. for the preemptive model, we introduce a polynomial time k-approximation algorithm. for the nonpreemptive model, we introduce a polynomial time o(k log2 k)-approximation algorithm.
entropy-based bounds for online algorithms. we focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request sequences for which all algorithms perform equally poorly. the motivations for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. to utilize these features, the operating system needs to identify data streams that can benefit from more resources. our approach in this work is based on the relation between entropy, compression, and gambling, extensively studied in information theory. it has been shown that in some settings, entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. we study bounds based on entropy for three classical online problems---list accessing, prefetching, and caching. our bounds relate the performance of the best online algorithm to the entropy, a parameter intrinsic to characteristics of the request sequence. this is in contrast to the competitive ratio parameter of competitive analysis, which quantifies the performance of the online algorithm with respect to an optimal offline algorithm. for the prefetching problem, we give explicit upper and lower bounds for the performance of the best prefetching algorithm in terms of the entropy of the request sequence. in contrast, we show that the entropy of the request sequence alone does not fully capture the performance of online list accessing and caching algorithms.
a data structure for a sequence of string accesses in external memory. we introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. formally, given a dictionary of n strings s1, &hellip;, sn, we aim at supporting a search sequence for m not necessarily distinct strings t1, t2, &hellip;, tm, as well as inserting and deleting individual strings. the dictionary is stored on disk, where each access to a disk page fetches b items, the cost of an operation is the number of pages accessed (i/os), and efficiency must be attained on entire sequences of string operations rather than on individual ones. our approach relies on a novel and conceptually simple self-adjusting data structure (sasl) based on skip lists, that is also interesting per se. the search for the whole sequence t1, t2, &hellip;, tm can be done in an expected number of i/os: o(&sum;j&equals;1m &verbar;tj&verbar;/b &plus; &sum;i&equals;1nn (ni logb m/ni)), where each tj may or may not be present in the dictionary, and ni is the number of times si is queried (i.e., the number of tjs equal to si). moreover, inserting or deleting a string si takes an expected amortized number o(&verbar;si&verbar;/b &plus; logb n) of i/os. the term &sum;j&equals;1m &verbar;tj&verbar;/b in the search formula is a lower bound for reading the input, and the term &sum;i&equals;1n ni logb m/ni (entropy of the query sequence) is a standard information-theoretic lower bound. we regard this result as the static optimality theorem for external-memory string access, as compared to sleator and tarjan's classical theorem for numerical dictionaries [sleator and tarjan 1985]. finally, we reformulate the search bound if a cache is available, taking advantage of common prefixes among the strings examined in the search.
algorithmic aspects of bandwidth trading. we study algorithmic problems that are motivated by bandwidth trading in next-generation networks. typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. the buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., internet subscribers). depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied. we model this as a real-time nonpreemptive scheduling problem in which machine types correspond to bandwidth pipes and jobs correspond to end-user reservation requests. each job specifies a time interval during which it must be processed, and a set of machine types on which it can be executed. if necessary, multiple machines of a given type may be allocated, but each must be paid for. finally, each job has associated with it a revenue, which is realized if the job is scheduled on some machine. there are two versions of the problem that we consider. in the cost minimization version, the goal is to minimize the total cost incurred for scheduling all jobs, and in the revenue maximization version the goal is to maximize the revenue of the jobs that are scheduled for processing on a given set of machines. we consider several variants of the problems that arise in practical scenarios, and provide constant factor approximations.
minimizing weighted flow time. we consider the problem of minimizing the total weighted flow time on a single machine with preemptions. we give an online algorithm that is o(k)-competitive for k weight classes. this implies an o(log w)-competitive algorithm, where w is the maximum to minimum ratio of weights. this algorithm also implies an o(log n &plus; log p)-approximation ratio for the problem, where p is the ratio of the maximum to minimum job size and n is the number of jobs. we also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. we consider the resource augmentation model, and give a (1 &plus; &epsiv;)-speed, (1 &plus;1/&epsiv;)-competitive online algorithm.
an () algorithm for incremental topological ordering. we present a simple algorithm which maintains the topological order of a directed acyclic graph (dag) with n nodes, under an online edge insertion sequence, in o(n2.75) time, independent of the number m of edges inserted. for dense dags, this is an improvement over the previous best result of o(min{m3/2 log n, m3/2 + n2 log n}) by katriel and bodlaender [2006]. we also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.
computing equilibria for a service provider game with (im)perfect information. we study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. suppose a provider offers a service to a set of potential customers. each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider.classical game theory assumes complete information: the provider has full knowledge of the behavior of all customers. we present a complete characterization of the complexity of computing optimal pricing strategies and of computing best/worst equilibria in this model. basically, we show that most of these problems are inapproximable in the worst case but admit an fpas in the average case. our average case analysis covers large classes of distributions for customer utilities. we generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.a more realistic model considers providers with incomplete information. following the game theoretic framework of bayesian games introduced by harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best/worst equilibria. somewhat counterintuitively, we obtain an fpras for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst-case measures. in particular, the worst-case complexity of the considered problems increases with the precision of the available knowledge.
improved approximation results for the stable marriage problem. the stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. it is np-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. in this article, we give the first nontrivial result for approximation of factor less than two. our algorithm achieves an approximation ratio of 2/(1 &plus; l&minus;2) for instances in which only men have ties of length at most l. when both men and women are allowed to have ties but the lengths are limited to two, then we show a ratio of 13/7(<1.858). we also improve the lower bound on the approximation ratio to 21/19(>1.1052).
dynamic text and static pattern matching. in this article, we address a new version of dynamic pattern matching. the dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. the goal is to report all new occurrences of the pattern in the text after each text update. we present an algorithm for solving the problem where the text update operation is changing the symbol value of a text location. given a text of length n and a pattern of length m, our algorithm preprocesses the text in time o(n log log m), and the pattern in time o(m log m). the extra space used is o(n &plus; m log m). following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in o(log log m) time. we note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.
compressed indexes for dynamic text collections. let t be a string with n characters over an alphabet of constant size. a recent breakthrough on compressed indexing allows us to build an index for t in optimal space (i.e., o(n) bits), while supporting very efficient pattern matching [ferragina and manzini 2000; grossi and vitter 2000]. yet the compressed nature of such indexes also makes them difficult to update dynamically. this article extends the work on optimal-space indexing to a dynamic collection of texts. our first result is a compressed solution to the library management problem, where we show an index of o(n) bits for a text collection l of total length n, which can be updated in o(&verbar;t&verbar; log n) time when a text t is inserted or deleted from l; also, the index supports searching the occurrences of any pattern p in all texts in l in o(&verbar;p&verbar; log n &plus; occ log2 n) time, where occ is the number of occurrences. our second result is a compressed solution to the dictionary matching problem, where we show an index of o(d) bits for a pattern collection d of total length d, which can be updated in o(&verbar;p&verbar; log2 d) time when a pattern p is inserted or deleted from d; also, the index supports searching the occurrences of all patterns of d in any text t in o((&verbar;t&verbar; &plus; occ)log2 d) time. when compared with the o(d log d)-bit suffix-tree-based solution of amir et al. [1995], the compact solution increases the query time by roughly a factor of log d only. the solution to the dictionary matching problem is based on a new compressed representation of a suffix tree. precisely, we give an o(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text t in o(&verbar;t&verbar; log2 n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. this work can be regarded as a generalization of the compressed representation of static texts. in the study of the aforementioned result, we also derive the first o(n)-bit representation for maintaining n pairs of balanced parentheses in o(log n/log log n) time per operation, matching the time complexity of the previous o(n log n)-bit solution.