waashk/dblp huggingface dataset:
better bounds for online scheduling. we study a classical problem in online scheduling. a sequence of jobs must be scheduled on m identical parallel machines. as each job arrives, its processing time is known. the goal is to minimize the makespan. bartal et al. [ j. comput. system sci., 51 (1995), pp. 359--366] gave a deterministic online algorithm that is 1.986-competitive. karger, phillips, and torng [ j. algorithms, 20 (1996), pp. 400--430] generalized the algorithm and proved an upper bound of 1.945. the best lower bound currently known on the competitive ratio that can be achieved by deterministic online algorithms is equal to 1.837. in this paper we present an improved deterministic online scheduling algorithm that is 1.923-competitive; for all $m\geq 2$. the algorithm is based on a new scheduling strategy, i.e., it is not a generalization of the approach by bartal et al. also, the algorithm has a simple structure. furthermore, we develop a better lower bound. we prove that, for general m, no deterministic online scheduling algorithm can be better than 1.852-competitive.
on paging with locality of reference. motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. in this paper, we propose a new, simple model for studying paging with locality of reference. the model is closely related to denning's working set concept and directly reflects the amount of locality that request sequences exhibit. we use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. we develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as lru, fifo, deterministic marking strategies and lfd. these bounds show that lru is an optimal online algorithm, whereas fifo and marking strategies are not optimal in general. we present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice.
reducibility, randomness, and intractability (abstract) the method of showing a problem np-complete by polynomial reduction is one of the most elegant and productive in our theory ([ 1 ], [ 3 ]). it is a means of providing compelling evidence that a problem in np is not in p. in this paper we will demonstrate new methods for showing this. our methods, based on a new notion of reducibility (gamma-reducibility) are apparently of more general applicability than that of polynomial reduction and are intended to be of practical value to researchers in the field. we use our methods to &ldquo;demonstrate&rdquo; (i.e., give compelling evidence) that some natural problems in np which are not known to be np-complete are, nonetheless, not in p.
minimizing stall time in single and parallel disk systems. we study integrated prefetching and caching problems following the work of cao et al. [1995] and kimbrel and karlin [1996]. cao et al. and kimbrel and karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk settings. the total elapsed time is the sum of the processor stall times and the length of the request sequence to be served.we show that an optimum prefetching/caching schedule for a single disk problem can be computed in polynomial time, thereby settling an open question by kimbrel and karlin. for the parallel disk problem, we give an approximation algorithm for minimizing stall time. the solution uses a few extra memory blocks in cache. stall time is an important and harder to approximate measure for this problem. all of our algorithms are based on a new approach which involves formulating the prefetching/caching problems as linear programs.
tradeoffs in probabilistic packet marking for ip traceback. there has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. an important consideration for such schemes is the number of packet header bits that need to be allocated to the marking protocol. let b denote this value. all previous schemes belong to a class of protocols for which b must be at least log n, where n is the number of bits used to represent the path of the packets. in this paper, we introduce a new marking technique for tracing a sequence of packets sent along the same path. this new technique is effective even when b=1. in other words, the sequence of packets can be traced back to their source using only a single bit in the packet header. with this scheme, the number of packets required to reconstruct the path is o(22n), but we also show that &omega;(2n) packets are required for any protocol where b=1. we also study the tradeoff between b and the number of packets required. we provide a protocol and a lower bound that together demonstrate that for the optimal protocol, the number of packets required (roughly) increases exponentially with n, but decreases doubly exponentially with b. the protocol we introduce is simple enough to be useful in practice. we also study the case where the packets are sent along k different paths. for this case, we demonstrate that any protocol must use at least log(2k&mdash;1) header bits. we also provide a protocol that requires &lceil;log(2k+1)&rceil; header bits in some restricted scenarios. this protocol introduces a new coding technique that may be of independent interest.
exploring unknown environments. we consider exploration problems where a robot has to construct a complete map of an unknown environment. we assume that the environment is modeled by a directed, strongly connected graph. the robot's task is to visit all nodes and edges of the graph using the minimum number r of edge traversals. deng and papadimitriou [ proceedings of the 31st symposium on the foundations of computer science, 1990, pp. 356--361] showed an upper bound for r of do(d) m and koutsoupias (reported by deng and papadimitriou) gave a lower bound of $\omega(d^2 m)$, where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph eulerian. we give the first subexponential algorithm for this exploration problem, which achieves an upper bound of do(log d) m. we also show a matching lower bound of $d^{\omega(\log d)}m$ for our algorithm. additionally, we give lower bounds of $2^{\omega(d)}m$, respectively, $d^{\omega(\log d)}m$ for various other natural exploration algorithms.
polynomial algorithms for linear programming over the algebraic numbers we derive an algorithm based on the ellipsoid method that solves linear programs whose coefficients are real algebraic numbers. by defining the encoding size of an algebraic number to be the bit size of the coefficients of its minimal polynomial, we prove the algorithm runs in time polynomial in the dimension of the problem, the encoding size of the input coefficients, and the degree of any algebraic extension which contains the input coefficients. this bound holds even if all input and arithmetic is performed symbolically, using rational numbers only.
on the performance of greedy algorithms in packet buffering. we study a basic buffer management problem that arises in network switches. consider $m$ input ports, each of which is equipped with a buffer (queue) of limited capacity. data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. in each time step the switch can transmit one packet from one of the buffers to the output port. the goal is to maximize the number of transmitted packets. simple arguments show that any work-conserving algorithm, which serves any nonempty buffer, is 2-competitive. azar and richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies. in practice, greedy algorithms are very important because they are fast, use little extra memory, and reduce packet loss by always serving a longest queue. in this paper we first settle the competitive performance of the entire family of greedy strategies. we prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. we also give improved lower bounds for deterministic and randomized online algorithms.in this paper we present the first deterministic online algorithm that is better than 2-competitive. we develop a modified greedy algorithm, called semigreedy, and prove that it achieves a competitive ratio of $17/9 \approx 1.89$. the new algorithm is simple, fast, and uses little extra memory. only when the risk of packet loss is low does it not serve the longest queue. additionally we study scenarios when an online algorithm is granted additional resources. we consider resource augmentation with respect to memory and speed; i.e., an online algorithm may be given larger buffers or higher transmission rates. we analyze greedy and other online strategies.
lower bounds for k-dnf resolution on random 3-cnfs. we prove exponential lower bounds for the refutation of a random 3-cnf with linear number of clauses by k-dnf resolution for k ≤ √ log n ⁄ log log n. for this we design a specially tailored random restrictions that preserve the structure of the input random 3-cnf while mapping every k-dnf with large covering number to 1 with high probability. next we make use of the switching lemma for small restrictions by segerlind, buss and impagliazzo to prove the lower bound.this work improves the previously known lower bound for res(2) system on random 3-cnfs by atserias, bonet and esteban and the result of segerlind, buss, impagliazzo stating that random o(k2)-cnf do not possess short res(k) refutations.
towards asymptotic optimality in probabilistic packet marking. there has been considerable recent interest in probabilistic packet marking schemes for sending information from nodes (routers) along one or more paths traveled by a stream of packets to the end-host receiving that stream. a central consideration for such schemes is the tradeoff between the number b of possible states of the marking bits in a packet, the number of bits n of information being sent by the nodes, and the expected number of packets t required to reconstruct this information. for the case where the packets all travel along the same path, we prove a lower bound of t ≥ ω(b22n/(b-1)), roughly the square of an earlier lower bound of adler.for an upper bound, we consider a model where each of m nodes along a single path must send one of s possible messages (thus n = m log2 s total bits are sent). we prove that t ≤ o(m • 22m(log2 s)/(b-1)) suffices (the implicit constant depends on b and s); this almost matches the lower bound, and is roughly the square root of an earlier upper bound of adler. the new bound holds for all b and s in two slightly relaxed models, while under the strictest requirements we prove it only for some special values of b and s. this is related to a challenging geometric problem: the existence of an s-reptile (b-1)-dimensional simplex, i.e. a simplex s that can be tiled by s congruent simplices similar to s.we also consider the case where the packets travel along multiple paths to the same destination. in this case, we present a new protocol and analysis technique that together allow us to significantly generalize over previous work the scenarios where the protocol is effective.
towards strong nonapproximability results in the lovasz-schrijver hierarchy. lovász and schrijver described a generic method of tightening the lp and sdp relaxation for any 0-1 optimization problem. these tightened relaxations were the basis of several celebrated approximation algorithms (such as for max-cu , max-3sat, and sparsest cut).we prove strong inapproximability results in this model for well-known problems such as max-3sat, hypergraph vertex cover and set cover. we show that the relaxations produced by as many as ω(n) rounds of the ls+ procedure do not allow nontrivial approximation, thus ruling out the possibility that the ls+ approach gives even slightly subexponential approximation algorithms for these problems.we also point out why our results are somewhat incomparable to known inapproximability results proved using pcps, and formalize several interesting open questions.
a stochastic process on the hypercube with applications to peer-to-peer networks. consider the following stochastic process executed on a graph g=(v,e) whose nodes are initially uncovered. in each step, pick a node at random and if it is uncovered, cover it. otherwise, if it has an uncovered neighbor, cover a random uncovered neighbor. else, do nothing. this can be viewed as a structured coupon collector process. we show that for a large family of graphs, o(n) steps suffice to cover all nodes of the graph with high probability, where n is the number of vertices. among these graphs are d-regular graphs with d =ω(log n log log n), random d-regular graphs with d =ω(log n) and the k-dimensional hypercube where n=2k.this process arises naturally in answering a question on load balancing in peer-to-peer networks. we consider a distributed hash table in which keys are partitioned across a set of processors, and we assume that the number of processors grows dynamically, starting with a single processor. if at some stage there are n processors, the number of queries required to find a key is log2 n+o(1), the number of pointers maintained by each processor is log2 n+o(1), and moreover the worst ratio between the loads of processors is o(1), with high probability. to the best of our knowledge, this is the first analysis of a distributed hash table that achieves asymptotically optimal load balance, while still requiring only o(log n) pointers per processor and o(log n) queries for locating a key; previous methods required ω(log2 n) pointers per processor and ω(log n) queries for locating a key.
space complexity in propositional calculus. we study space complexity in the framework of propositional proofs. we consider a natural model analogous to turing machines with a read-only input tape and such popular propositional proof systems as resolution, polynomial calculus, and frege systems. we propose two different space measures, corresponding to the maximal number of bits, and clauses/monomials that need to be kept in the memory simultaneously. we prove a number of lower and upper bounds in these models, as well as some structural results concerning the clause space for resolution and frege systems.
an exponential separation between regular and general resolution. two distinct proofs of an exponential separation between regular resolution and unrestricted resolution are given. the previous best known separation between these systems was quasi-polynomial.
a simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension it has been a challenge for mathematicians to confirm theoretically the extremely good performance of simplex-type algorithms for linear programming. in this paper the average number of steps performed by a simplex algorithm, the so-called self-dual method, is analyzed. the algorithm is not started at the traditional point (1, &hellip; , l)t, but points of the form (1, &egr;, &egr;2, &hellip;)t, with &egr; sufficiently small, are used. the result is better, in two respects, than those of the previous analyses. first, it is shown that the expected number of steps is bounded between two quadratic functions c1(min(m, n))2 and c2(min(m, n))2 of the smaller dimension of the problem. this should be compared with the previous two major results in the field. borgwardt proves an upper bound of o(n4m1/(n-1)) under a model that implies that the zero vector satisfies all the constraints, and also the algorithm under his consideration solves only problems from that particular subclass. smale analyzes the self-dual algorithm starting at (1, &hellip; , 1)t. he shows that for any fixed m there is a constant c(m) such the expected number of steps is less than c(m)(ln n)m(m+1); megiddo has shown that, under smale's model, an upper bound c(m) exists. thus, for the first time, a polynomial upper bound with no restrictions (except for nondegeneracy) on the problem is proved, and, for the first time, a nontrivial lower bound of precisely the same order of magnitude is established. both borgwardt and smale require the input vectors to be drawn from spherically symmetric distributions. in the model in this paper, invariance is required only under certain
quantitative solution of omega-regular games. we consider two-player games played for an infinite number of rounds, with ω-regular winning conditions. the games may be concurrent, in that the players choose their moves simultaneously and independently, and probabilistic, in that the moves determine a probability distribution for the successor state. we introduce quantitative game µ-calculus, and we show that the maximal probability of winning such games can be expressed as the fixpoint formulas in this calculus. we develop the arguments both for deterministic and for probabilistic concurrent games; as a special case, we solve probabilistic turn-based games with ω-regular winning conditions, which was also open. we also characterize the optimality, and the memory requirements, of the winning strategies. in particular, we show that while memoryless strategies suffice for winning games with safety and reachability conditions, büchi conditions require the use of strategies with infinite memory. the existence of optimal strategies, as opposed to ε-optimal, is only guaranteed in games with safety winning conditions.
some consequences of the existence of pseudorandom generators if secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. if sets in p must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up deterministic computation. connections are drawn between pseudorandom generation, generalized kolmogorov complexity, and immunity properties of complexity classes.
expanders, sorting in rounds and superconcentrators of limited depth expanding graphs and superconcentrators are relevant to theoretical computer science in several ways. here we use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges. our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using &ogr;(n&agr;k) processors, where, e.g., &agr;2 = 7/4. using our graphs we can also construct efficient n-superconcentrators of limited depth. for example, we construct an n superconcentrator of depth 3 with &ogr;(n4/3) edges; better than the previous known results.
the online set cover problem. let $x=\{1,2,\ldots,n\}$ be a ground set of $n$ elements, and let ${\cal s}$ be a family of subsets of $x$, $|{\cal s}|=m$, with a positive cost $c_s$ associated with each $s\in{\cal s}$. consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. an adversary gives elements to the algorithm from $x$ one by one. once a new element is given, the algorithm has to cover it by some set of ${\cal s}$ containing it. we assume that the elements of $x$ and the members of ${\cal s}$ are known in advance to the algorithm; however, the set $x'\subseteq x$ of elements given by the adversary is not known in advance to the algorithm. (in general, $x'$ may be a strict subset of $x$.) the objective is to minimize the total cost of the sets chosen by the algorithm. let ${\cal c}$ denote the family of sets in ${\cal s}$ that the algorithm chooses. at the end of the game the adversary also produces (offline) a family of sets ${\cal c}_{opt}$ that covers $x'$. the performance of the algorithm is the ratio between the cost of ${\cal c}$ and the cost of ${\cal c}_{opt}$. the maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. we present an $o(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of $m$ and $n$. the techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the winnow algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.
a random nc algorithm for depth first search in this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. the algorithm is an rnc algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a p-ram. the run time of the algorithm is &ogr;(tmm(n)log3n), and the number of processors used is pmm(n) where tmm(n) and pmm(n) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.
routing permutations on graphs via matchings. a class of routing problems on connected graphs $g$ is considered. initially, each vertex $v$ of $g$ is occupied by a ``pebble'' that has a unique destination $\pi (v)$ in $g$ (so that $\pi$ is a permutation of the vertices of $g$). it is required that all the pebbles be routed to their respective destinations by performing a sequence of moves of the following type: a disjoint set of edges is selected, and the pebbles at each edge's endpoints are interchanged. the problem of interest is to minimize the number of steps required for any possible permutation $\pi$. this paper investigates this routing problem for a variety of graphs $g$, including trees, complete graphs, hypercubes, cartesian products of graphs, expander graphs, and cayley graphs. in addition, this routing problem is related to certain network flow problems, and to several graph invariants including diameter, eigenvalues, and expansion coefficients.
a model for hierarchical memory in this paper we introduce the hierarchical memory model (hmm) of computation. it is intended to model computers with multiple levels in the memory hierarchy. access to memory location x is assumed to take time &lceil; log x &rceil;. tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and fft. efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. it is shown that the circuit simulation problem has inherently poor locality of reference. the results are extended to hmm's where memory access time is given by an arbitrary (nondecreasing) function. tight upper and lower bounds are obtained for hmm's with polynomial memory access time; the algorithms for searching, fft and matrix multiplication are shown to be optimal for arbitrary memory access time. on-line memory management algorithms for the hmm model are also considered. an algorithm that uses lru policy at the successive &ldquo;levels&rdquo; of the memory hierarchy is shown to be optimal.