waashk/dblp huggingface dataset:
optimality of an algorithm solving the bottleneck tower of hanoi problem. we study the bottleneck tower of hanoi puzzle posed by d. wood in 1981. there, a relaxed placement rule allows a larger disk to be placed higher than a smaller one if their size difference is less than a pregiven value k. a shortest sequence of moves (optimal algorithm) transferring all the disks placed on some peg in decreasing order of size, to another peg in the same order is in question. in 1992, d. poole suggested a natural disk-moving strategy for this problem, and computed the length of the shortest move sequence under its framework. however, other strategies were overlooked, so the lower bound/optimality question remained open. in 1998, benditkis, berend, and safro proved the optimality of poole's algorithm for the first nontrivial case k &equals; 2. we prove poole's algorithm to be optimal in the general case.
on network design problems: fixed cost flows and the covering steiner problem. network design problems, such as generalizations of the steiner tree problem, can be cast as edge-cost-flow problems. an edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying positive flow.we prove a hardness result for the minimum edge cost flow problem (mecf). using the one-round two-prover scenario, we prove that mecf does not admit a 2log1-&epsiv; n-ratio approximation, for every constant &epsiv; > 0, unless np &sube; dtime(npolylogn).a restricted version of mecf, called infinite capacity mecf (icf), is defined. the icf problem is defined as follows: (i) all edges have infinite capacity, (ii) there are multiple sources and sinks, where flow can be delivered from every source to every sink, (iii) each source and sink has a supply amount and demand amount, respectively, and (iv) the required total flow is given as part of the input. the goal is to find a minimum edge-cost flow that meets the required total flow while obeying the demands of the sinks and the supplies of the sources. this problem naturally arises in practical scheduling applications, and is equivalent to the special case of single source mecf, with all edges not touching the source or the sink having infinite capacity.the directed icf generalizes the covering steiner problem in directed and undirected graphs. the undirected version of icf generalizes several network design problems, such as: steiner tree problem, k-mst, point-to-point connection problem, and the generalized steiner tree problem.an o(log x)-approximation algorithm for undirected icf is presented. we also present a bi-criteria approximation algorithm for directed icf. the algorithm for directed icf finds a flow that delivers half the required flow at a cost that is at most o(n&epsiv;/&epsiv;4) times bigger than the cost of an optimal flow. the running time of the algorithm is o(x2/&epsiv; &cdot; n1+1/&epsiv;), where x denotes the required total flow.randomized approximation algorithms for the covering steiner problem in directed and undirected graphs are presented. the algorithms are based on a randomized reduction to a problem called 1/2-group steiner. in undirected graphs, the approximation ratio matches the approximation ratio of konjevod et al. [2002]. however, our algorithm is much simpler. in directed graphs, the algorithm is the first nontrivial approximation algorithm for the covering steiner problem. deterministic algorithms are obtained by derandomization.
balanced parentheses strike back. an ordinal tree is an arbitrary rooted tree where the children of each node are ordered. succinct representations for ordinal trees with efficient query support have been extensively studied. the best previously known result is due to geary et al. [2004b, pages 1--10]. the number of bits required by their representation for an n-node ordinal tree t is 2n + o(n), whose first-order term is information-theoretically optimal. their representation supports a large set of o(1)-time queries on t. based upon a balanced string of 2n parentheses, we give an improved 2n + o(n)-bit representation for t. our improvement is two-fold: first, the set of o(1)-time queries supported by our representation is a proper superset of that supported by the representation of geary, raman, and raman. second, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.
improved algorithms for the minmax-regret 1-center and 1-median problems. in this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. for the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from o(mn2 log n) to o(mn log n). for the problem on a tree, we improve the upper bound from o(n2) to o(n log2 n). for the minmax-regret 1-median problem on a general graph, we improve the upper bound from o(mn2 log n) to o(mn2 + n3 log n). for the problem on a tree, we improve the upper bound from o(n log2 n) to o(n log n).
algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. in the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. in this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. the capacity of a line bounds the number of rectangles that the line can cover. we consider two versions of this problem. in the first, one is allowed to use only a single copy of each line (hard capacities), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution (soft capacities). we present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. this algorithm is also extended to solve a certain capacitated multi-item lot-sizing inventory problem with joint set-up costs. for the case of d-dimensional rectangle stabbing with soft capacities, we present a 3d-approximation algorithm for the unweighted case. for d-dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4d-approximate solutions that use at most two copies of every line. finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.
analysis of linear combination algorithms in cryptography. several cryptosystems rely on fast calculations of linear combinations in groups. one way to achieve this is to use joint signed binary digit expansions of small &ldquo;weight.&rdquo; we study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. both methods are sped up using the sliding windows approach combined with precomputed lookup tables. we give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. expected values, variances and a central limit theorem are proved using generating functions.furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. this avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.
individual displacements for linear probing hashing with different insertion policies. we study the distribution of the individual displacements in hashing with linear probing for three different versions: first come, last come and robin hood. asymptotic distributions and their moments are found when the the size of the hash table tends to infinity with the proportion of occupied cells converging to some &alpha;, 0 < &alpha; < 1. (in the case of last come, the results are more complicated and less complete than in the other cases.)we also show, using the diagonal poisson transform studied by poblete, viola and munro, that exact expressions for finite m and n can be obtained from the limits as m,n &rarr; &infin;.we end with some results, conjectures and questions about the shape of the limit distributions. these have some relevance for computer applications.
writing-all deterministically and optimally using a nontrivial number of asynchronous processors. the problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. this article considers an abstraction of this problem called write-all: using p processors write 1's into all locations of an array of size n. in this problem writing 1 abstracts the notion of performing a simple task. despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for write-all/. efficiency of algorithms is measured in terms of work that accounts for all local steps performed by the processors in solving the problem. thus, an optimal algorithm would have work &theta;(n), however it is known that optimality cannot be achieved when p &equals; &omega;(n). the quest then is to obtain work-optimal solutions for this problem using a nontrivial, compared to n, number of processors p. the algorithm presented in this article has work complexity of o(n + p2 + &epsi;), and it achieves work optimality for p &equals; o(n1/(2 + &epsiv;)) for any &epsiv; > 0, while the previous best result achieved optimality for p&le;4&sqrt;n/log n. additionally, the new result uses only the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution.
the np-completeness column. this is the 24th edition of a column that covers new developments in the theory of np-completeness. the presentation is modeled on that which m. r. garey and i used in our book &ldquo;computers and intractability: a guide to the theory of np-completeness,&rdquo; w. h. freeman & co., new york, 1979, hereinafter referred to as &ldquo;[g&j].&rdquo; previous columns, the first 23 of which appeared in j. algorithms, will be referred to by a combination of their sequence number and year of appearance, e.g. &ldquo;[col 1, 1981].&rdquo; this edition of the column describes the history and purpose of the column and the status of the open problems from [g&j] and previous columns.
optimally scheduling video-on-demand to minimize delay when sender and receiver bandwidth may differ. we establish tight bounds on the intrinsic cost (either minimizing delay d for fixed sender and receiver bandwidths, or minimizing sender bandwidth for fixed delay and receiver bandwidth) of broadcasting a video of length m over a channel of bandwidth s in such a way that a receiver (with bandwidth r), starting at an arbitrary time s, can download the video so that it can begin playback at time s &plus; d.our bounds are realized by a simple just-in-time protocol that partitions the video into a fixed number of segments, partitions the sender bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its own subchannel. the protocol is suitable for the broadcast of compressed video and it can be implemented so that video information is packaged into discrete fixed length packets incurring only a modest overhead (measured in terms of increased delay).our primary contribution is a lower bound on the required delay that applies to all protocols. this lower bound matches the behavior of our just-in-time protocol in the limit as the number of segments approaches infinity, provided the video compression satisfies some uniform upper bound. for a fixed number of segments, our protocol is optimal within a broad class of protocols, even if the video is compressed arbitrarily.
approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design. given an undirected graph g = (v,e) with nonnegative costs on its edges, a root node r v, a set of demands d v with demand v d wishing to route w(v) units of flow (weight) to r, and a positive number k, the capacitated minimum steiner tree (cmstt) problem asks for a minimum steiner tree, rooted at r, spanning the vertices in d * lcub;r rcub;, in which the sum of the vertex weights in every subtree connected to r is at most k. when d equals; v, this problem is known as the capacitated minimum spanning tree (cmst) problem. both cmst and cmst problems are np-hard. in this article, we present approximation algorithms for these problems and several of their variants in network design. our main results are the following: ---we present a (&sup3; &aacute;st + 2)-approximation algorithm for the cmstt problem, where &sup3; is the inverse steiner ratio, and &aacute;st is the best achievable approximation ratio for the steiner tree problem. our ratio improves the current best ratio of 2&aacute;st + 2 for this problem. ---in particular, we obtain (&sup3; + 2)-approximation ratio for the cmst problem, which is an improvement over the current best ratio of 4 for this problem. for points in euclidean and rectilinear planes, our result translates into ratios of 3.1548 and 3.5, respectively. ---for instances in the plane, under the lp norm, with the vertices in d having uniform weights, we present a nontrivial (7/5&aacute;st + 3/2)-approximation algorithm for the cmstt problem. this translates into a ratio of 2.9 for the cmst problem with uniform vertex weights in the lpmetric plane. our ratio of 2.9 solves the long-standing open problem of obtaining any ratio better than 3 for this case. ---for the cmst problem, we show how to obtain a 2-approximation for graphs in metric spaces with unit vertex weights and k = 3,4. ---for the budgeted cmst problem, in which the weights of the subtrees connected to r could be up to &plusmn; k instead of k (&plusmn; e 1), we obtain a ratio of &sup3; plus; 2/&plusmn;.
approximation schemes for wireless networks. wireless networks are created by the communication links between a collection of radio transceivers. the nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. in contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information. on such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. we apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. these are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. however, the approach is presented in a general fashion since it can be applied to other problems as well. the approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an np-hard problem).
problems column. computing professionals must beware when exclusive rights tip out of balance with obligations, unreasonably invalidating intellectual capital.
atomic congestion games among coalitions. we consider algorithmic questions concerning the existence, tractability, and quality of nash equilibria, in atomic congestion games among users participating in selfish coalitions. we introduce a coalitional congestion model among atomic players and demonstrate many interesting similarities with the noncooperative case. for example, there exists a potential function proving the existence of pure nash equilibria (pne) in the unrelated parallel links setting; in the network setting, the finite improvement property collapses as soon as we depart from linear delays, but there is an exact potential (and thus pne) for linear delays. the price of anarchy on identical parallel links demonstrates a quite surprising threshold behavior: it persists on being asymptotically equal to that in the case of the noncooperative kp-model, unless the number of coalitions is sublogarithmic. we also show crucial differences, mainly concerning the hardness of algorithmic problems that are solved efficiently in the noncooperative case. although we demonstrate convergence to robust pne, we also prove the hardness of computing them. on the other hand, we propose a generalized fully mixed nash equilibrium that can be efficiently constructed in most cases. finally, we propose a natural improvement policy and prove its convergence in pseudopolynomial time to pne which are robust against (even dynamically forming) coalitions of small size.
a linear-time approximation algorithm for weighted matchings in graphs. approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. here we propose an approximation algorithm for the weighted matching problem in graphs which can be solved in polynomial time. the weighted matching problem is to find a matching in an edge weighted graph that has maximum weight. the first polynomial-time algorithm for this problem was given by edmonds in 1965. the fastest known algorithm for the weighted matching problem has a running time of o(nm+n2log n). many real world problems require graphs of such large size that this running time is too costly. therefore, there is considerable need for faster approximation algorithms for the weighted matching problem. we present a linear-time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3. this improves the previously best performance ratio of 1/2. our algorithm is not only of theoretical interest, but because it is easy to implement and the constants involved are quite small it is also useful in practice.
approximation algorithms for a facility location problem with service capacities. we present the first constant-factor approximation algorithms for the following problem. given a metric space (v, c), a finite set d &sube; v of terminals/customers with demands d : d &rarr; r+, a facility opening cost f &isin; r+ and a capacity u &isin;r+, find a partition d &equals; d1&cupdot;&hellip;&cupdot;dk and steiner trees ti for di (i &equals; 1, &hellip;,k) with c(e(ti)) + d(di) &le; u for i &equals; 1,&hellip;,k such that &sumi &equals; 1k c(e(ti)) + kf is minimum. this problem arises in vlsi design. it generalizes the bin-packing problem and the steiner tree problem. in contrast to other network design and facility location problems, it has the additional feature of upper bounds on the service cost that each facility can handle. among other results, we obtain a 4.1-approximation in polynomial time, a 4.5-approximation in cubic time, and a 5-approximation as fast as computing a minimum spanning tree on (d, c).
exact distribution of individual displacements in linear probing hashing. this paper studies the distribution of individual displacements for the standard and the robin hood linear probing hashing algorithms. when the a table of size m has n elements, the distribution of the search cost of a random element is studied for both algorithms. specifically, exact distributions for fixed m and n are found as well as when the table is &alpha;-full, and &alpha; strictly smaller than 1. moreover, for full tables, limit laws for both algorithms are derived.
label-guided graph exploration by a finite automaton. a finite automaton, simply referred to as a robot, has to explore a graph, that is, visit all the nodes of the graph. the robot has no a priori knowledge of the topology of the graph, nor of its size. it is known that for any k-state robot, there exists a graph of maximum degree 3 that the robot cannot explore. this article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. we describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. we also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. in other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot r, and a way to color in black or white the nodes of any bounded-degree graph g, so that r can explore the colored graph g. finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).
fast sparse matrix multiplication. let a and b two n&times;n matrices over a ring r (e.g., the reals or the integers) each containing at most m nonzero elements. we present a new algorithm that multiplies a and b using o(m0.7n1.2+n2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over r. the na&iuml;ve matrix multiplication algorithm, on the other hand, may need to perform &ohm;(mn) operations to accomplish the same task. for m&le;n1.14, the new algorithm performs an almost optimal number of only n2+o(1) operations. for m&le;n1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses o(n2.38) algebraic operations. the new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. we also obtain improved algorithms for the multiplication of more than two sparse matrices. as the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.
algorithmic construction of sets for -restrictions. this work addresses k-restriction problems, which unify combinatorial problems of the following type: the goal is to construct a short list of strings in &sigma;m that satisfies a given set of k-wise demands. for every k positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. problems of this form frequently arise in different fields in computer science.the standard approach for deterministically solving such problems is via almost k-wise independence or k-wise approximations for other distributions. we offer a generic algorithmic method that yields considerably smaller constructions. to this end, we generalize a previous work of naor et al. [1995]. among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct multi-way splitters, using a new discrete version of the topological necklace splitting theorem [alon 1987].we utilize our methods to show improved constructions for group testing [ngo and du 2000] and generalized hashing [alon et al. 2003], and an improved inapproximability result for set-cover under the assumption p &neq; np.