waashk/dblp huggingface dataset:
routing selfish unsplittable traffic. we consider general resource assignment games involving selfish users/agents in which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). we propose and study a mechanism design approach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user to truthfully report a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). this information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her). for our resource allocation problems, we give an algorithmic characterization of the solutions for which truth-telling is a nash equilibrium. a natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of koutsoupias and papadimitriou [1999]: each selfish user wants to route a piece of unsplittable traffic using one of m links of different speeds so as to minimize his/her own latency. our mechanism design counterpart can be seen as the problem of scheduling selfish jobs on parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallel selfish machines studied by archer and tardos [2001]. koutsoupias and papadimitriou studied an &ldquo;anarchic&rdquo; scenario in which each user chooses his/her own link, and this may produce nash equilibria of cost &omega;(log m/log log m) times the optimum. our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). we indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). however, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. this result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by archer and tardos (which admits exact solutions). we also study some generalizations of this basic problem.
approximation algorithms and hardness results for cycle packing problems. the cycle packing number &nu;e(g) of a graph g is the maximum number of pairwise edge-disjoint cycles in g. computing &nu;e(g) is an np-hard problem. we present approximation algorithms for computing &nu;e(g) in both undirected and directed graphs. in the undirected case we analyze a variant of the modified greedy algorithm suggested by caprara et al. [2003] and show that it has approximation ratio &theta;(&sqrt;log n), where n &equals; &verbar;v(g)&verbar;. this improves upon the previous o(log n) upper bound for the approximation ratio of this algorithm. in the directed case we present a &sqrt;n-approximation algorithm. finally, we give an o(n2/3)-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset s of vertices. we also study generalizations of these problems. our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the integrality gap of standard lp-relaxations of these problems. in addition, we give lower bounds for the integrality gap and approximability of &nu;e(g) in directed graphs. specifically, we prove a lower bound of &omega;(log n/loglog n) for the integrality gap of edge-disjoint cycle packing. we also show that it is quasi-np-hard to approximate &nu;e(g) within a factor of o(log1 &minus; &epsiv; n) for any constant &epsiv; > 0. this improves upon the previously known apx-hardness result for this problem.
packing element-disjoint steiner trees. given an undirected graph g(v, e) with terminal set t &sube; v, the problem of packing element-disjoint steiner trees is to find the maximum number of steiner trees that are disjoint on the nonterminal nodes and on the edges. the problem is known to be np-hard to approximate within a factor of &omega;(log n), where n denotes &verbar;v&verbar;. we present a randomized o(log n)-approximation algorithm for this problem, thus matching the hardness lower bound. moreover, we show a tight upper bound of o(log n) on the integrality ratio of a natural linear programming relaxation.
the -traveling repairmen problem. we consider the k-traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. we give a polynomial-time 8.497&alpha;-approximation algorithm for this generalization, where &alpha; denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. for the latter problem, a (2 &plus; &epsiv;)-approximation is known. our results can be compared with the best-known approximation algorithm using similar techniques for the case k &equals; 1, which is 3.59&alpha;. moreover, recent work of chaudry et al. [2003] shows how to remove the factor of &alpha;, thus improving all of these results by that factor. we are aware of no previous work on the approximability of the present problem. in addition, we give a simple proof of the 3.59&alpha;-approximation result that can be more easily extended to the case of multiple repairmen, and may be of independent interest.
improved online algorithms for buffer management in qos switches. we consider the following buffer management problem arising in qos networks: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. packets not forwarded before their deadlines are lost. the main result of the article is an online 64/33 &ap; 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. for the 2-uniform case we give an algorithm with ratio &ap; 1.377 and a matching lower bound.
partial fillup and search time in lc tries. andersson and nilsson introduced in 1993 a level-compressed trie (for short, lc trie) in which a full subtree of a node is compressed to a single node of degree being the size of the subtree. recent experimental results indicated a &ldquo;dramatic improvement&rdquo; when full subtrees are replaced by &ldquo;partially filled subtrees.&rdquo; in this article, we provide a theoretical justification of these experimental results, showing, among others, a rather moderate improvement in search time over the original lc tries. for such an analysis, we assume that n strings are generated independently by a binary memoryless source, with p denoting the probability of emitting a &ldquo;1&rdquo; (and q &equals; 1 &minus; p). we first prove that the so-called &alpha;-fillup level fn(&alpha;) (i.e., the largest level in a trie with &alpha; fraction of nodes present at this level) is concentrated on two values with high probability: either fn(&alpha;) &equals; kn or fn(&alpha;) &equals; kn &plus; 1, where kn &equals; log1/&sqrt;pq n &minus; &verbar;ln (p/q)&verbar;/2 ln3/2 (1&sqrt;pq) &phi;&minus;1 (&alpha;) &sqrt; ln n &plus; o(1) is an integer and &phi;(x) denotes the normal distribution function. this result directly yields the typical depth (search time) dn(&alpha;) in the &alpha;-lc tries, namely, we show that with high probability dn(&alpha;) &sim; c2 log log n, where c2 &equals; 1/&verbar;log(1 &minus; h/log(1/&sqrt;pq))&verbar; for p &ne; q and h &equals; &minus;plog p&minus;qlog q is the shannon entropy rate. this should be compared with recently found typical depth in the original lc tries, which is c1log log n, where c1 &equals; 1/&verbar;log(1&minus;h/log(1/min&lcub;p, 1&minus;p&rcub;))&verbar;. in conclusion, we observe that &alpha; affects only the lower term of the &alpha;-fillup level fn(&alpha;), and the search time in &alpha;-lc tries is of the same order as in the original lc tries.
edge-disjoint paths revisited. the approximability of the maximum edge-disjoint paths problem (edp) in directed graphs was seemingly settled by an &omega;(m1/2 &minus; &epsis;)-hardness result of guruswami et al. [2003], and an o(&sqrt;m) approximation achievable via a natural multicommodity-flow-based lp relaxation as well as a greedy algorithm. here m is the number of edges in the graph. we observe that the &omega;(m1/2 &minus; &epsis;)-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n, that is, the number of vertices, only an &omega;(n1/2&minus; &epsis;)-hardness follows. on the other hand, o(&sqrt;m)-approximation algorithms do not guarantee a sublinear (in terms of n) approximation algorithm for dense graphs. we note that a similar gap exists in the known results on the integrality gap of the flow-based lp relaxation: an &omega;(&sqrt;n) lower bound and o(&sqrt;m) upper bound. motivated by this discrepancy in the upper and lower bounds, we study algorithms for edp in directed and undirected graphs and obtain improved approximation ratios. we show that the greedy algorithm has an approximation ratio of o(min(n2/3, &sqrt;m)) in undirected graphs and a ratio of o(min(n4/5, &sqrt;m)) in directed graphs. for acyclic graphs we give an o(&sqrt;n ln n) approximation via lp rounding. these are the first sublinear approximation ratios for edp. the results also extend to edp with weights and to the uniform-capacity unsplittable flow problem (ucufp).
succinct indexable dictionaries with applications to encoding -ary trees, prefix sums and multisets. we consider the indexable dictionary problem, which consists of storing a set s &sube; &lcub;0,&hellip;,m &minus; 1&rcub; for some integer m while supporting the operations of rank(x), which returns the number of elements in s that are less than x if x &isin; s, and &minus;1 otherwise; and select(i), which returns the ith smallest element in s. we give a data structure that supports both operations in o(1) time on the ram model and requires b(n, m) &plus; o(n) &plus; o(lg lg m) bits to store a set of size n, where b(n, m) &equals; &lfloor;lg (m/n)&rfloor; is the minimum number of bits required to store any n-element subset from a universe of size m. previous dictionaries taking this space only supported (yes/no) membership queries in o(1) time. in the cell probe model we can remove the o(lg lg m) additive term in the space bound, answering a question raised by fich and miltersen [1995] and pagh [2001]. we present extensions and applications of our indexable dictionary data structure, including: &mdash;an information-theoretically optimal representation of a k-ary cardinal tree that supports standard operations in constant time; &mdash;a representation of a multiset of size n from &lcub;0,&hellip;,m &minus; 1&rcub; in b(n, m &plus; n) &plus; o(n) bits that supports (appropriate generalizations of) rank and select operations in constant time; and &plus; o(lg lg m) &mdash;a representation of a sequence of n nonnegative integers summing up to m in b(n, m &plus; n) &plus; o(n) bits that supports prefix sum queries in constant time.
algorithms for power savings. this article examines two different mechanisms for saving power in battery-operated embedded systems. the first strategy is that the system can be placed in a sleep state if it is idle. however, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. the second way in which power savings can be achieved is by varying the speed at which jobs are run. we utilize a power consumption curve p(s) which indicates the power consumption level given a particular speed. we assume that p(s) is convex, nondecreasing, and nonnegative for s &ge; 0. the problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. we assume that all jobs can be preempted and resumed at no cost. although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. we give an offline algorithm that is within a factor of 2 of the optimal algorithm. we also give an online algorithm with a constant competitive ratio.
the priority r-tree: a practically efficient and worst-case optimal r-tree. we present the priority r-tree, or pr-tree, which is the first r-tree variant that always answers a window query using o((n/b)1&minus;1/d&plus;t/b) i/os, where n is the number of d-dimensional (hyper-) rectangles stored in the r-tree, b is the disk block size, and t is the output size. this is provably asymptotically optimal and significantly better than other r-tree variants, where a query may visit all n/b leaves in the tree even when t &equals; 0. we also present an extensive experimental study of the practical performance of the pr-tree using both real-life and synthetic data. this study shows that the pr-tree performs similarly to the best-known r-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.
approximate distance oracles for geometric spanners. given an arbitrary real constant &epsiv; > 0, and a geometric graph g in d-dimensional euclidean space with n points, o(n) edges, and constant dilation, our main result is a data structure that answers (1 &plus; &epsiv;)-approximate shortest-path-length queries in constant time. the data structure can be constructed in o(n log n) time using o(n log n) space. this represents the first data structure that answers (1 &plus; &epsiv;)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. the data structure is also applied to several other problems. in particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with &ldquo;rounded&rdquo; obstacles can be answered in constant time. other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. finally, we show how to extend the main result to answer (1 &plus; &epsiv;)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m &equals; &omega;(n) edges. the resulting data structure can be constructed in o(m &plus; n log n) time using o(n log n) space.
improved bounds for scheduling conflicting jobs with minsum criteria. we consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. the conflicts among jobs are formed as an arbitrary conflict graph. building on the framework of queyranne and sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, (k &plus; 1)-claw-free graphs, and perfect graphs. in particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. we also improve the results of kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling.
rectangular layouts and contact graphs. contact graphs of isothetic rectangles unify many concepts from applications including vlsi and architectural design, computational geometry, and gis. minimizing the area of their corresponding rectangular layouts is a key problem. we study the area-optimization problem and show that it is np-hard to find a minimum-area rectangular layout of a given contact graph. we present o(n)-time algorithms that construct o(n2)-area rectangular layouts for general contact graphs and o(n log n)-area rectangular layouts for trees. (for trees, this is an o(log n)-approximation algorithm.) we also present an infinite family of graphs (respectively, trees) that require &omega;(n2) (respectively, &omega;(n log n))area. we derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of rectangular duals. a corollary to our results relates the class of graphs that admit rectangular layouts to rectangle-of-influence drawings.
path decomposition under a new cost measure with applications to optical network design. we introduce a problem directly inspired by its application to dwdm (dense wavelength division multiplexing) network design. we are given a set of demands to be carried over a network. our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. these paths are called optical line systems. the cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. this cost metric is motivated by the need to minimize o-e-o (optical-electrical-optical) conversions in optical transmission. for given line systems, it is easy to find the optimal demand routes. on the other hand, for given demand routes designing the optimal line systems can be np-hard. we first present a 2-approximation for general network topologies. as optical networks often have low node degrees, we offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3. our solution is based on a local greedy approach. if neither demand routes nor line systems are fixed, the situation becomes much harder. even for a restricted scenario on a 3-regular hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. for general topologies, we offer a simple algorithm with an o(log k)- and an o(log n)-approximation, where k is the number of demands and n the number of nodes. this approximation ratio is almost tight. for rings, a common special topology, we offer a more complex 3/2-approximation algorithm.
thin heaps, thick heaps. the fibonacci heap was devised to provide an especially efficient implementation of dijkstra's shortest path algorithm. although asyptotically efficient, it is not as fast in practice as other heap implementations. expanding on ideas of h&oslash;yer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps) that have the same amortized efficiency as fibonacci heaps, but need less space and promise better practical performance. as part of our development, we fill in a gap in h&oslash;yer's analysis.
alternation and redundancy analysis of the intersection problem. the intersection of sorted arrays problem has applications in search engines such as google. previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a certificate of the result (cost analysis). we define the alternation analysis, based on the nondeterministic complexity of an instance. in this analysis we prove that there is a deterministic algorithm asymptotically performing as well as any randomized algorithm in the comparison model. we define the redundancy analysis, based on a measure of the internal redundancy of the instance. in this analysis we prove that any algorithm optimal in the redundancy analysis is optimal in the alternation analysis, but that there is a randomized algorithm which performs strictly better than any deterministic algorithm in the comparison model. finally, we describe how these results can be extended beyond the comparison model.
the collective memory of amnesic processes. this article considers the problem of robustly emulating a shared atomic memory over a distributed message-passing system where processes can fail by crashing and possibly recover. we revisit the notion of atomicity in the crash-recovery context and introduce a generic algorithm that emulates an atomic memory. the algorithm is instantiated for various settings according to whether processes have access to local stable storage, and whether, in every execution of the algorithm, a sufficient number of processes are assumed not to crash. we establish the optimality of specific instances of our algorithm in terms of resilience, log complexity (number of stable storage accesses needed in every read or write operation), as well as time complexity (number of communication steps needed in every read or write operation). the article also discusses the impact of considering a multiwriter versus a single-writer memory, as well as the impact of weakening the consistency of the memory by providing safe or regular semantics instead of atomicity.
uniform deterministic dictionaries. we present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting &ldquo;good&rdquo; hash functions. the main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. the model of computation is the word ram, and it is assumed that the machine word-size matches the size of keys in bits. many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at &ldquo;compile time&rdquo; for the stated time bounds to hold. the currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. in contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. our family of dynamic dictionaries achieves a performance of the following type: lookups in time o(t) and updates in amortized time o(n1/t), for an appropriate parameter function t. update procedures require division, whereas searching uses multiplication only.
randomized minimum spanning tree algorithms using exponentially fewer random bits. for many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best-known deterministic algorithm. among these are the minimum spanning tree (mst) problem, the mst sensitivity analysis problem, the parallel connected components and parallel minimum spanning tree problems, and the local sorting and set maxima problems. (for the first two problems there are provably optimal deterministic algorithms with unknown, and possibly superlinear, running times.) one downside of the randomized methods for solving these problems is that they use a number of random bits linear in the size of input. in this article we develop some general methods for reducing exponentially the consumption of random bits in comparison-based algorithms. in some cases we are able to reduce the number of random bits from linear to nearly constant, without affecting the expected running time. most of our results are obtained by adjusting or reorganizing existing randomized algorithms to work well with a pairwise or o(1)-wise independent sampler. the prominent exception, and the main focus of this article, is a linear-time randomized minimum spanning tree algorithm that is not derived from the well-known karger-klein-tarjan algorithm. in many ways it resembles more closely the deterministic minimum spanning tree algorithms based on soft heaps. further, using our algorithm as a guide, we present a unified view of the existing &ldquo;nongreedy&rdquo; minimum spanning tree algorithms. concepts from the karger-klein-tarjan algorithm, such as f-lightness, mst verification, and sampled graphs, are related to the concepts of edge corruption, subgraph contractibility, and soft heaps, which are the basis of the deterministic mst algorithms of chazelle and pettie-ramachandran.