waashk/dblp huggingface dataset:
network design for information networks. we define a new class of network design problems motivated by designing information networks. in our model, the cost of transporting flow for a set of users (or servicing them by a facility) depends on the amount of information requested by the set of users. we assume that the aggregation cost follows economies of scale, that is, the incremental cost of a new user is less if the set of users already served is larger. naturally, information requested by some sets of users might aggregate better than that of others, so our cost is now a function of the actual set of users. not just their total demand.we provide constant-factor approximation algorithms to two important problems in this general model. in the group facility location problem, each user needs information about a resource. and the cost is a linear function of the number of resources involved (instead of the number of clients served). the dependent maybecast problem extends the karger-minkoff maybecast model to probabilities with limited correlation and also contains the 2-stage stochastic optimization problem as a special case. we also give an o(ln n)-approximation algorithm for the single sink information network design problem.we show that the stochastic steiner tree problem can be approximated by dependent maybecast, and using this we obtain an o(1)-approximation algorithm for the k-stage stochastic steiner tree problem for any fixed k. this is the first approximation algorithm for multi-stage stochastic optimization. our algorithm allows scenarios to have different inflation factors, and works for any distribution provided that we can sample the distribution.
polynomial time recognition of p4-structure. a p4 is a set of four vertices of a graph that induces a chordless path; the p4-structure of a graph is the set of all p4's. va&scaron;ek chv&aacute;tal asked if there is a polynomial time algorithm to determine whether an arbitrary four-uniform hypergraph is the p4-structure of some graph. the answer is yes; we present such an algorithm.
a categorization theorem on suffix arrays with applications to space efficient text indexes. in this paper, we design succinct index structures for a text string t of n binary symbols to support efficient searching of a pattern p of length m. motivated by the fact that the standard representation of suffix arrays uses n lg n bits which is more than the theoretical minimum, we present a theorem that characterizes a permutation as the suffix array of a binary string. based on the theorem, we design a succinct representation of suffix arrays of binary strings that uses n + o(n) bits, which is the theoretical minimum plus a lower order term, and answers existential and cardinality queries in o(m) time without storing the raw text. with 2n+o(n) bits, we can list pattern occurrences in o(m + occ lg n) time in the general case, and for long patterns, when m = &omega;(lg1+&isin; n), we answer such listing queries in o(m + occ) time. we also present another implementation that uses o(n) bits and supports pattern searching in o(m + occ lg&lambda; n) time for any fixed &lambda; such that 0 < &lambda; < 1. more results and trade-offs are reported in the paper.
edge coloring planar graphs with two outerplanar subgraphs. the standard problem of edge coloring a graph with k colors is equivalent to partitioning the edge set of the graph into k matchings. here edge coloring is generalized by replacing matchings with outerplanar graphs. we give a polynomial-time algorithm that edge colors any planar graph with two outerplanar subgraphs. two is clearly minimal for the class of planar graphs. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
scheduling multicasts on unit-capacity trees and meshes. this paper studies the multicast routing and admission control problem on unit-capacity tree and mesh topologies in the throughput model. the problem is a generalization of the edge-disjoint paths problem and is np-hard both on trees and meshes. we study both the offline and the online version of the problem: in the offline setting, we give the first constant-factor approximation algorithm for trees, and an o((log log n)2)-factor approximation algorithm for meshes. in the online setting, we give the first polylogarithmic competitive online algorithm for tree and mesh topologies. no polylogarithmiccompetitive algorithm is possible on general network topologies (lower bounds for on-line graph problems with application to on-line circuits and optical routing, in: proceedings of the 28th acm symposium on theory of computing, 1996, pp. 531-540) and there exists a polylogarithmic lower bound on the competitive ratio of any online algorithm on tree topologies (making commitments in the face of uncertainity: how to pick a winner almost every time, in: proceedings of the 28th annual acm symposium on theory of computing, 1996, pp. 519-530). we prove the same lower bound for meshes.
simplified kinetic connectivity for rectangles and hypercubes. we consider the problem of maintaining connected components in a set of moving objects using the kinetic data structure (kds) framework. we assume that the motion of each object can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. while the objects move continuously, their connectivity changes at discrete times. a straightforward dynamic graph approach for maintaining connectivity of n objects has three shortcomings: the graph can have &ohgr;(n2) edges, the update bounds are amortized, and the algorithm is very complicated. our first result shows that the connectivity for a set of n moving hypercubes can be maintained using a very simple, easy to determine graph with &ogr;(n) edges. but this graph still requires a general-purpose dynamic graph scheme for connectivity maintenance. our main result is a simplified connectivity data structure for moving rectangles in the plane. for this special but important case, we are able to overcome all three shortcomings mentioned above: our graph has &ogr;(n) edges; our data structure supports updates in &ogr;(log2 n) worst-case time; and the algorithm and data structures are quite a bit simpler than those based on a general dynamic graph scheme.
binary space partitions for 3d subdivisions. we consider the following question: given a subdivision of space into n convex polyhedral cells, what is the worst-case complexity of a binary space partition (bsp) for the subdivision? we show that if the subdivision is rectangular and axis-aligned, then the worstcase complexity of an axis-aligned bsp is &omega;(n4/3) and o(n&alpha; log2 n), where &alpha; = 1 + log2(4/3 ) = 1.4150375 .... by contrast, it is known that the bsp of a collection of n rectangular cells not forming a subdivision has worstcase complexity &theta;(n3/2). we also show that the worstcase complexity of a bsp for a general convex polyhedral subdivision of total complexity o(n) is &omega;(n3/2).
directed graphs requiring large numbers of shortcuts. a conjecture by thorup is that the diameter of a directed graph with n vertices and m edges can be reduced to (log n)o(1) by adding o(m) edges [3]. we give a counterexample to this conjecture. we construct a graph g requiring the addition of &omega;(mn 1/17) edges to reduce its diameter below &theta;(n1/17). by extending the construction to higher dimensions, we construct graphs with n1+&epsilon; edges that require the addition of &omega;(n2--&epsilon;) edges to reduce their diameter. these constructions yield time-space tradeoffs in lower bounds for transitive closure queries in a certain computational model.
a note on the nearest neighbor in growth-restricted metrics. in this paper, we give results relevant to sequential and distributed dynamic data structures for finding nearest neighbors in growth-restricted metrics. our sequential data structure uses linear space, and requires o(log n) queries in expecation and o(log n) queries for lookups with high probability. this improves the results of karger and ruhl [4], whose data structure uses o(n log n) space with comparable expected time bounds. this also improves on the time bound of a load-balanced version of algorithm (for dynamic networks) presented in [3].our algorithm was inspired by the object location data structure developed by plaxton, rajaraman and richa [6], and is similar in structure to the algorithm of krauthgamer and lee [5]. it is significantly different that of karger and ruhl [4].a distributed version of the algorithm presented here is in use as a part of tapestry [3, 8], a peer-to-peer object location system based on [6].
symmetric drawings of triconnected planar graphs. symmetry is one of the most important aesthetic criteria in graph drawing because it reveals structure in the graph. to draw graphs symmetrically, we need two steps. the first step is to find appropriate automorphisms. the second step is to draw the graph to display the automorphisms. our aim in this paper is to construct maximally symmetric straight-line drawings of triconnected planar graphs in linear time. previously known algorithms run in quadratic time. we show that an algorithm of fontet can be used to find an embedding in the plane with the maximum number of symmetries, and present a new algorithm for finding a straight line drawing that achieves that maximum. both algorithms run in linear time.
geometric permutations of high dimensional spheres. we prove the maximum number of geometric permutations, induced by line transversals to a set of n pairwise disjoint congruent spheres in rd with d &gne; 3, is no more than 4 when n is sufficiently large, achieving the best known upper bound for this problem. we also prove the maximum number of geometric permutations of a set of n noncongruent spheres of bounded radius ratio in rd, d &gne; 3, is at most 2[&radic;2m]+1, where m is the ratio or the largest radius and the smallest radius. our result settles a conjecture in combinatorial geometry.
on efficient unsuccessful search. this paper introduces a general technique for speeding up unsuccessful search using very little extra space (2 bits per key). this technique is applicable to many data structures including linear lists, and search trees. for linear lists we get on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. in a virtual memory environment our self-adjusting algorithm for multi-way search trees is competitive with an optimal static multi-way tree and will often outperform the static tree.
optimal planar point location. given a fixed distribution of point location queries among the regions of a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time.
alternatives to splay trees with o(log n) worst-case access times. splay trees are a self adjusting form of search tree that supports access operations in &ogr;(log n) amortized time. splay trees also have several amazing distribution sensitive properties, the strongest two of which are the working set theorem and the dynamic finger theorem. however, these two theorems are shown to poorly bound the performance of splay trees on some simple access sequences. the unified conjecture is presented, which subsumes the working set theorem and dynamic finger theorem, and accurately bounds the performance of splay trees over some classes of sequences where the existing theorems' bounds are not tight. while the unified conjecture for splay trees is unproven, a new data structure, the unified structure, is presented where the unified conjecture does hold. this structure also has a worst case of &ogr;(log n) per operation, in contrast to the &ogr;(n) worst case runtime of splay trees. a second data structure, the working set structure, is introduced. the working set structure has the same performance attributed to splay trees through the working set theorem, except the runtime is worst case per operation rather than amortized.
approximating vertex cover on dense graphs. although many problems in max-snp admit a ptas for dense graphs, that is not the case for vertex cover, which is max-snp hard even for dense graphs. this paper presents a randomized approximation algorithm for vertex cover on dense graphs, i.e., graphs whose average degree d is &omega;(n). (i) our algorithm improves the best-known bound for the approximation factor by karpinski and zelikovsky. for example, our bound is 2/1 + d/2&delta; for dense graphs such that |e| &le; &delta;(n - &delta;) where &delta; is the maximum degree. the improvement is especially large when d &ap; &delta;; if d &ge; 2/3&delta; for instance, our bound is at most 1.5 while the previous bound approaches to 2.0 as n/&delta; increases. (ii) it achieves the same factor for a wider range of graphs, i.e., for the graphs whose &delta; is &omega;(n log log n/log n). (iii) it is probably optimal in the sense that if we can achieve a better approximation factor by &delta; > 0 for the above range of graphs, then we can achieve a factor of 2 - &delta; for general graphs.
on the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. combinatorial optimization is often used to "plan ahead," purchasing and allocating resources for demands that are not precisely known at the time of solution. this advance planning may be done because resources become very expensive to purchase or difficult to allocate at the last minute when the demands are known. in this work we study the tradeoffs involved in making some purchase/allocation decisions early to reduce cost while deferring others at greater expense to take advantage of additional, late-arriving information. we consider a number of combinatorial optimization problems in which the problem instance is uncertain---modeled by a probability distribution---and in which solution elements can be purchased cheaply now or at greater expense after the distribution is sampled. we show how to approximately optimize the choice of what to purchase in advance and what to defer.
marriage, honesty, and stability. many centralized two-sided markets form a matching between participants by running a stable marriage algorithm. it is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. however, as we will show in this paper, in a probabilistic setting where the preference lists of one side of the market are composed of only a constant (independent of the the size of the market) number of entries, each drawn from an arbitrary distribution, the number of participants that have more than one stable partner is vanishingly small. this proves (and generalizes) a conjecture of roth and peranson [23]. as a corollary of this result, we show that, with high probability, the truthful strategy is the best response for a given player when the other players are truthful. we also analyze equilibria of the deferred acceptance stable marriage game. we show that the game with complete information has an equilibrium in which a (1 - o(1)) fraction of the strategies are truthful in expectation. in the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a (1 + o(1))-approximate bayesian-nash equilibrium. our results have implications in many practical settings and were inspired by the work of roth and peranson [23] on the national residency matching program.
limitations of cross-monotonic cost sharing schemes. a cost-sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) amongs serviced customers. a cost-sharing scheme is cross-monotonic if it satisfies the property that everyone is better off when the set of people who receive the service expands. in this article, we develop a novel technique for proving upper bounds on the budget-balance factor of cross-monotonic cost-sharing schemes or the worst-case ratio of recovered cost to total cost. we apply this technique to games defined, based on several combinatorial optimization problems, including the problems of edge cover, vertex cover, set cover, and metric facility location and, in each case, derive tight or nearly-tight bounds. in particular, we show that for the facility location game, there is no cross-monotonic cost-sharing scheme that recovers more than a third of the total cost. this result, together with a recent 1/3-budget-balanced cross-monotonic cost-sharing scheme of p&aacute;l and tardos &lsqb;2003&rsqb; closes the gap for the facility location game. for the vertex cover and set cover games, we show that no cross-monotonic cost-sharing scheme can recover more than a o(n&minus;1/3) and o(1/n) fraction of the total cost, respectively. finally, we study the implications of our results on the existence of group-strategyproof mechanisms. we show that every group-strategyproof mechanism corresponds to a cost-sharing scheme that satisfies a condition weaker than cross-monotonicity. using this, we prove that group-strategyproof mechanisms satisfying additional properties give rise to cross-monotonic cost-sharing schemes and therefore our upper bounds hold.
explicit constructions of selectors and related combinatorial structures, with applications. in this paper we present explicit constructions of several combinatorial objects: selectors [cgr00] and selective families [cggpr00], pseudo-random generators for proof systems [abrw00] and fixed waking schedules [gpp00]. as a result, we obtain almost optimal deterministic protocols for broadcasting in unknown directed radio networks [cgr00] and wake-up problem [gpp00]. we also show application of selectors (and its variants) to explicit construction of test sets for coin-weighting problems [dh00]. the parameters of our constructions come close to the best known non-constructive bounds. the constructions are achieved using a common technique, which could be of use for other problems.
better algorithms for high-dimensional proximity problems via asymmetric embeddings. in this paper we give several results based on randomized embeddings of l2 into l&infin;(or "l&infin;-like") spaces. our first result is a (1 + &epsilon;)-distortion asymmetric embedding of n points in l2 into l&infin; with polylog(n) dimension, for any 1 + &epsilon;. this gives the first known o(1)- approximate nearest neighbor algorithm with fast query time and almost polynomial space for a product of euclidean norms, a common generalization of both l2 and l&infin; norms. our embedding also clarifies the relative complexity of approximate nearest neighbor in l2 and l&infin; spaces.our second result in a (1 + &epsilon;)-approximate algorithm for the diameter of n points in ld2, running in time &otilde;(dn1+l/(1+&epsilon;)2); the algorithm is fully dynamic. this improves several previous algorithms for this problem (see table 1 for more information).
approximate nearest neighbor under edit distance via product metrics. we present a data structure for the approximate nearest neighbor problem under edit metric (which is defined as the minimum number of insertions, deletions and character substitutions needed to transform one string into another). for any l &ge; 1 and a set of n strings of length d, the data structure reports a 3l-approximate nearest neighbor for any given query string q in o(d) time. the space requirement of this data structure is roughly o(nd1/(l+1)), i.e., strongly subexponential. to our knowledge, this is the first data structure for this problem with both o(n) query time and storage subexponential in d.
approximate congruence in nearly linear time. the problem of geometric point set matching has been studied extensively in the domain of computational geometry, and has many applications in areas such as computer vision, computational chemistry, and pattern recognition. one of the commonly used metrics is the bottleneck distance, which for two point sets p and q is the minimum over all one-to-one mappings f : p → q of maxp∈pd(p,f(p)), where d is the euclidean distance. much effort has gone into developing efficient algorithms for minimising the bottleneck distance between two point sets under groups of transformations. however, the algorithms that have thus far been developed suffer from running times that are large polynomials in the size of the input, even for approximate formulations of the problem.in this paper we define a point set similarity measure that includes both the bottleneck distance and the hausdorff distance as special cases. this measure relaxes the condition that the mapping must be one-to-one, but guarantees that only a few points are mapped to any point. using a novel application of hall's theorem to reduce the geometric matching problem to a combinatorial matching problem, we present near-linear time approximation schemes for minimising this distance between two point sets in the plane under isometries; we note here that the best known algorithms for congruence under the bottleneck measure run in time õ(n2.5).we also obtain a combinatorial bound on the metric entropy of certain families of geometric objects. this result yields improved algorithms for approximate congruence, and may be of independent interest.
strongly competitive algorithms for paging with locality of reference. what is the best paging algorithm if one has partial information about the possible sequences of page requests? we give a partial answer to this question, by presenting the analysis of strongly competitive paging algorithms in the access graph model. this model restricts page requests so that they conform to a notion of locality of reference, given by an arbitrary access graph. we first consider optimal algorithms for undirected access graphs. borodin et al. [2] define an algorithm, called far, and proved that it is within a logarithmic factor of the optimal. we prove that far is in fact strongly competitive, i.e. within a constant factor of the optimum. for directed access graphs, we present an algorithm that is strongly competitive on all structured program graphs&mdash;graphs modeling the request sequences of structured programs.
probabilistic analysis for scheduling with conflicts. in this paper, we consider scheduling jobs that may be competing for mutually exclusive resources. we model the conflicts between jobs with a conflict graph, so that all concurrently running jobs must form an independent set in the graph. our goal is to bound the maximum response time of any job in the system. we adopt a discrete model of time and assume that each job requires one time unit to be completed once it is started. it has been previously shown [s. irani, v. leung, scheduling with conflicts, and applications to traffic signal control, in: proceedings of the seventh annual acm-siam symposium on discrete algorithms, siam, 1996] that the best competitive ratio achievable by any online algorithm is @w(n), where n is the number of nodes in the graph. as a result, we study scheduling with conflicts under probabilistic assumptions about the input. each node i has a value p"i such that a job arrives at node i in any given time unit with probability p"i. arrivals at different nodes and during different time periods are independent. under reasonable assumptions on the value for the p"i's, we are able to obtain a bounded competitive ratio for an arbitrary conflict graph. in addition, if the conflict graph is a perfect graph, we give an algorithm whose competitive ratio converges to 1.