waashk/dblp huggingface dataset:
compact dictionaries for variable-length keys and data with applications. we consider the problem of maintaining a dynamic dictionary t of keys and associated data for which both the keys and data are bit strings that can vary in length from zero up to the length w of a machine word. we present a data structure for this variable-bit-length dictionary problem that supports constant time lookup and expected amortized constant-time insertion and deletion. it uses o(m &plus; 3n &minus; nlog2n) bits, where n is the number of elements in t, and m is the total number of bits across all strings in t (keys and data). our dictionary uses an array a&lsqb;1 &hellip; n&rsqb; in which locations store variable-bit-length strings. we present a data structure for this variable-bit-length array problem that supports worst-case constant-time lookups and updates and uses o(m &plus; n) bits, where m is the total number of bits across all strings stored in a. the motivation for these structures is to support applications for which it is helpful to efficiently store short varying-length bit strings. we present several applications, including representations for semidynamic graphs, order queries on integers sets, cardinal trees with varying cardinality, and simplicial meshes of d dimensions. these results either generalize or simplify previous results.
dissections, orientations, and trees with applications to optimal mesh encoding and random sampling. we present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees with interesting consequences for enumeration, mesh compression, and graph sampling. our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best-known uniform random sampler for labelled planar graphs. it also provides an encoding for the set p(n) of n-edge 3-connected planar graphs that matches the entropy bound 1/n log2 &verbar;p(n)&verbar; &equals; 2 &plus; o(1) bits per edge (bpe). this solves a theoretical problem recently raised in mesh compression as these graphs abstract the combinatorial part of meshes with spherical topology. we also achieve the optimal parametric rate 1/n log2 &verbar;p(n, i, j)&verbar; bpe for graphs of p(n) with i vertices and j faces, matching in particular the optimal rate for triangulations. our encoding relies on a linear time algorithm to compute an orientation associated with the minimal schnyder wood of a 3-connected planar map. this algorithm is of independent interest, and it is, for instance, a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs.
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.
dynamic routing schemes for graphs with low local density. this article studies approximate distributed routing schemes on dynamic communication networks. the work focuses on dynamic weighted general graphs where the vertices of the graph are fixed, but the weights of the edges may change. our main contribution concerns bounding the cost of adapting to dynamic changes. the update efficiency of a routing scheme is measured by the time needed in order to update the routing scheme following a weight change. a naive dynamic routing scheme, which updates all vertices following a weight change, requires &omega;(diam) time in order to perform the updates after every weight change, where diam is the diameter of the underlying graph. in contrast, this article presents approximate dynamic routing schemes with average time complexity &theta;&tilde;(d) per topological change, where d is the local density parameter of the underlying graph. following a weight change, our scheme never incurs more than diam time; thus, our scheme is particularly efficient on graphs which have low local density and large diameter. the article also establishes upper and lower bounds on the size of the databases required by the scheme at each site.
getting the best response for your erg. we consider the speed scaling problem of minimizing the average response time of a collection of dynamically released jobs subject to a constraint a on energy used. we propose an algorithmic approach in which an energy optimal schedule is computed for a huge a, and then the energy optimal schedule is maintained as a decreases. we show that this approach yields an efficient algorithm for equi-work jobs. we note that the energy optimal schedule has the surprising feature that the job speeds are not monotone functions of the available energy. we then explain why this algorithmic approach is problematic for arbitrary work jobs. finally, we explain how to use the algorithm for equi-work jobs to obtain an algorithm for arbitrary work jobs that is o(1)-approximate with respect to average response time, given an additional factor of (1 + &epsi;) energy.
improved algorithms for optimal embeddings. in the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. the notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum lipschitz and bi-lipschitz constants. one reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. the better distortion, the better the effectiveness of the original algorithm applied to a new metric space. the goal recently studied by kenyon et al. [2004] is to consider all possible embeddings between two finite metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. in this article we continue this important direction. in particular, using a theorem of albert and atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. this improves the previous bound of 3 + 2&sqrt;2, solving an open question posed by kenyon et al. [2004]. further, we show an inherent limitation of algorithms using the &ldquo;forbidden pattern&rdquo; based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4&sqrt;3 (&sime; 13.928). thus, our results are almost optimal for this method. we also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.
fully dynamic algorithms for chordal graphs and split graphs. we present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality; and (2) delete or insert an arbitrary edge, provided it preserves chordality. we give two implementations. in the first, each operation runs in o(n) time, where n is the number of vertices. in the second, an insertion query runs in o(log2 n) time, an insertion in o(n) time, a deletion query in o(n) time, and a deletion in o(n log n) time. we also present a data structure that allows a deletion query to run in o(&sqrt;m) time in either implementation, where m is the current number of edges. updating this data structure after a deletion or insertion requires o(m) time. we also present a very simple dynamic algorithm that supports each of the following operations in o(1) time on a general graph: (1) query whether the graph is split, and (2) delete or insert an arbitrary edge.
deterministic conflict-free coloring for intervals: from offline to online. we investigate deterministic algorithms for a frequency assignment problem in cellular networks. the problem can be modeled as a special vertex coloring problem for hypergraphs: in every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). we concentrate on a special case of the problem, called conflict-free coloring for intervals. we introduce a hierarchy of four models for the aforesaid problem: (i) static, (ii) dynamic offline, (iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. in the dynamic offline model, we give a deterministic algorithm that uses at most log3/2 n + 1 &;approx; 1.71 log2 n colors and show inputs that force any algorithm to use at least 3 log5 n + 1 &approx; 1.29 log2 n colors. for the online absolute-positions model, we give a deterministic algorithm that uses at most 3&lceil;log3 n&rceil; &approx; 1.89 log2 n colors. to the best of our knowledge, this is the first deterministic online algorithm using o(log n) colors in a nontrivial online model. in the online relative-positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the first-fit greedy online algorithm. we also consider conflict-free coloring only with respect to intervals that contain at least one of the two extreme points.
the relative worst order ratio applied to seat reservation. the seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations enroute in an online manner. the performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new measure for the quality of online algorithms, which allows for direct comparisons between algorithms. this study has yielded new separations between algorithms. for example, for both variants of the problem considered, using the relative worst order ratio, first-fit and best-fit are shown to be better than worst-fit.
multipartite priority queues. we introduce a framework for reducing the number of element comparisons performed in priority-queue operations. in particular, we give a priority queue which guarantees the worst-case cost of o(1) per minimum finding and insertion, and the worst-case cost of o(log n) with at most log n + o(1) element comparisons per deletion, improving the bound of 2 log n + o(1) known for binomial queues. here, n denotes the number of elements stored in the data structure prior to the operation in question, and log n equals log2(max {2, n}). as an immediate application of the priority queue developed, we obtain a sorting algorithm that is optimally adaptive with respect to the inversion measure of disorder, and that sorts a sequence having n elements and i inversions with at most n log (i/n) + o(n) element comparisons.
on the minimum common integer partition problem. we introduce a new combinatorial optimization problem in this article, called the minimum common integer partition (mcip) problem, which was inspired by computational biology applications including ortholog assignment and dna fingerprint assembly. a partition of a positive integer n is a multiset of positive integers that add up to exactly n, and an integer partition of a multiset s of integers is defined as the multiset union of partitions of integers in s. given a sequence of multisets s1, s2, &hellip;, sk of integers, where k &ge; 2, we say that a multiset is a common integer partition if it is an integer partition of every multiset si, 1 &le; i &le; k. the mcip problem is thus defined as to find a common integer partition of s1, s2, &hellip;, sk with the minimum cardinality, denoted as mcip(s1, s2, &hellip;, sk). it is easy to see that the mcip problem is np-hard, since it generalizes the well-known subset sum problem. we can in fact show that it is apx-hard. we will also present a 5/4-approximation algorithm for the mcip problem when k &equals; 2, and a 3k(k&minus;1)/3k&minus;2-approximation algorithm for k &ge; 3.
online nonpreemptive scheduling of equal-length jobs on two identical machines. we consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. our objective is to maximize the number of jobs completed by their deadlines. using standard nomenclature, this problem is denoted as p2 &verbar; pj &equals; p,rj &verbar; &sum; &uhorbar;j. the problem is known to be polynomially solvable in an offline setting. in an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. we present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. a simple lower bound shows that this is the optimal deterministic competitiveness.
kinetic and dynamic data structures for closest pair and all nearest neighbors. we present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. if no insertions or deletions take place, the structure for the closest pair uses o(n log n) space, and processes o(n2&beta;s+2(n)log n) critical events, each in o(log2n) time. here s is the maximum number of times where the distances between any two specific pairs of points can become equal, &beta;s(q) &equals; &lambda;s(q)/q, and &lambda;s(q) is the maximum length of davenport-schinzel sequences of order s on q symbols. the dynamic version of the problem incurs a slight degradation in performance: if m &ge; n insertions and deletions are performed, the structure still uses o(n log n) space, and processes o(mn&beta;s+2(n)log3 n) events, each in o(log3n) time. our kinetic data structure for all nearest neighbors uses o(n log2 n) space, and processes o(n2&beta;2s+2(n)log3 n) critical events. the expected time to process all events is o(n2&beta;s+22(n) log4n), though processing a single event may take &theta;(n) expected time in the worst case. if m &ge; n insertions and deletions are performed, then the expected number of events is o(mn&beta;2s+2(n) log3n) and processing them all takes o(mn&beta;2s+2(n) log4n). an insertion or deletion takes o(n) expected time.
combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. we provide an algorithm listing all minimal dominating sets of a graph on n vertices in time o(1.7159n). this result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159n, thus improving on the trivial o(2n/&sqrt;n) bound. our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. based on this result, we derive an o(2.8718n) algorithm for the domatic number problem.
algorithms for center and tverberg points. given a set s of n points in r3, a point x in r3 is called center point of s if every closed halfspace whose bounding hyperplane passes through x contains at least &lceil;n/4&rceil; points from s. we present a near-quadratic algorithm for computing the center region, that is the set of all center points, of a set of n points in r3. this is nearly tight in the worst case since the center region can have &omega;(n2) complexity. we then consider sets s of 3n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. a point x in r2 is called a colored tverberg point of s if there is a partition of s into n triples with one point of each color, so that x lies in all triangles spanned by these triples. we present a first polynomial-time algorithm for recognizing whether a given point is a colored tverberg point of such a 3-colored set s.
competitive buffer management for shared-memory switches. we consider buffer management policies for shared memory switches. we study the case of overloads resulting in packet loss, where the constraint is the limited shared memory capacity. the goal of the buffer management policy is that of maximizing the number of packets transmitted. the problem is online in nature, and thus we use competitive analysis to measure the performance of the buffer management policies. our main result is to show that the well-known preemptive longest queue drop (lqd) policy is at most 2-competitive and at least &sqrt;2-competitive. we also demonstrate a general lower bound of 4/3 on the performance of any deterministic online policy. finally, we consider some other popular non-preemptive policies including complete partition, complete sharing, static threshold and dynamic threshold and derive almost tight bounds on their performance.
srpt optimally utilizes faster machines to minimize flow time. we analyze the shortest remaining processing time (srpt) algorithm with respect to the problem of scheduling n jobs with release times on m identical machines to minimize total flow time. it is known that srpt is optimal if m &equals; 1 but that srpt has a worst-case approximation ratio of &theta;(min(log n/m, log &delta;)) for this problem, where &delta; is the ratio of the length of the longest job divided by the length of the shortest job. it has previously been shown that srpt is able to use faster machines to produce a schedule as good as an optimal algorithm using slower machines. we now show that srpt optimally uses these faster machines with respect to the worst-case approximation ratio. that is, if srpt is given machines that are s &ge; 2 &minus; 1/m times as fast as those used by an optimal algorithm, srpt's flow time is at least s times smaller than the flow time incurred by the optimal algorithm. clearly, no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to srpt without resource augmentation do not optimally use extra resources.
structure and linear-time recognition of 4-leaf powers. a graph g is the k-leaf power of a tree t if its vertices are leaves of t such that two vertices are adjacent in g if and only if their distance in t is at most k. then t is a k-leaf root of g. this notion was introduced and studied by nishimura, ragde, and thilikos [2002], motivated by the search for underlying phylogenetic trees. their results imply an o(n3)-time recognition algorithm for 4-leaf powers. recently, rautenbach [2006] as well as dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. we give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. as a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.
on hard instances of approximate vertex cover. we show that if there is a 2 &minus; &epsis; approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + &delta;, then there is a 2 &minus; f(&epsis;, &delta;) approximation algorithm for vertex cover for all graphs.
on an infinite family of solvable hanoi graphs. the tower of hanoi problem is generalized by placing pegs on the vertices of a given directed graph g with two distinguished vertices, s and d, and allowing moves only along arcs of this graph. an optimal solution for such a graph g is an algorithm that completes the task of moving a tower of any given number of disks from s to d in a minimal number of disk moves. in this article we present an algorithm which solves the problem for two infinite families of graphs, and prove its optimality. to the best of our knowledge, this is the first optimality proof for an infinite family of graphs. furthermore, we present a unified algorithm that solves the problem for a wider family of graphs and conjecture its optimality.
distributed weighted vertex cover via maximal matchings. in this article, we consider the problem of computing a minimum-weight vertex-cover in an n-node, weighted, undirected graph g &equals; (v,e). we present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. our algorithm runs in an expected number of o(log n + log &wcirc;) communication rounds, where &wcirc; is the average vertex-weight. the previous best algorithm for this problem requires o(log n(log n + log&wcirc;)) rounds and it is not fully distributed. for a maximal matching m in g, it is a well-known fact that any vertex-cover in g needs to have at least &verbar;m&verbar; vertices. our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.
combinatorial dominance guarantees for problems with infeasible solutions. the design and analysis of approximation algorithms for np-hard problems is perhaps the most active research area in the theory of combinatorial algorithms. in this article, we study the notion of a combinatorial dominance guarantee as a way for assessing the performance of a given approximation algorithm. an f(n) dominance bound is a guarantee that the heuristic always returns a solution not worse than at least f(n) solutions. we give tight analysis of many heuristics, and establish novel and interesting dominance guarantees even for certain inapproximable problems and heuristic search algorithms. for example, we show that the maximal matching heuristic of vertex cover offers a combinatorial dominance guarantee of 2n &minus; (1.839 + o(1))n. we also give inapproximability results for most of the problems we discuss.
a 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. we present a 1.8-approximation algorithm for the following np-hard problem: given a connected graph g &equals; (v, e) and an edge set e on v disjoint to e, find a minimum-size subset of edges f &sube; e such that (v, e &cup; f) is 2-edge-connected. our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + &epsiv; of nagamochi.