waashk/dblp huggingface dataset:
large the price of routing unsplittable flow. the essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. the splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. the unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.in this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. we show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. these results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. we also show that for polynomials of degree d edge latency functions the price of anarchy is dδ(d). our results hold also for mixed strategies.previous results of roughgarden and tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.
minimizing the flow time without migration. we consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). the performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption, i.e., interrupt a job and later continue its execution, perhaps migrating it to a different machine. preemption is inherent to make a scheduling algorithm efficient. while in the case of a single processor most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead. thus, it is not commonly used in most multiprocessor operating systems. the natural question is whether migration is an inherent component for an efficient scheduling algorithm in either the online or offline setting.leonardi and raz [proceedings of the twenty-ninth annual acm symposium on theory of computing, el paso, tx, 1997, pp. 110--119] showed that the well-known algorithm, shortest remaining processing time (srpt), performs within a logarithmic factor of the optimal offline algorithm. note that srpt must use both preemption and migration to schedule the jobs. it is not known if better approximation factors can be reached and thus srpt, although it is an online algorithm, becomes the best known algorithm in the offline setting. in fact, in the online setting, leonardi and raz showed that no algorithm can achieve a better bound.without migration, no (offline or online) approximations are known. this paper introduces a new algorithm that does not use migration, works online, and is just as effective (in terms of approximation ratio) as the best known offline algorithm that uses migration.
reducing truth-telling online mechanisms to online optimization. we describe a general technique for converting an online algorithm β to a truthtelling mechanism. we require that the original online competitive algorithm has certain "niceness" properties in that actions on future requests are independent of the actual value of requests which were accepted (though these actions will of course depend upon the set of accepted requests). under these conditions, we are able to give an online truthtelling mechanism (where the values of requests are given by bids which may not accurately represent the valuation of the requesters) such that our total profit is within o(ρ + log μ) of the optimum offline profit obtained by an omniscient algorithm (one which knows the true valuations of the users). here ρ is the competitive ratio of β for the optimization version of the problem, and μ is the ratio of the maximum to minimum valuation for a request. in general there is an ω(log μ) lower bound on the ratio of worst-case profit for a truthtelling mechanism when compared to the profit obtained by an omniscient algorithm, so this result is in some sense best possible. in addition, we prove that our construction is resilient against many forms of "cheating" attempts, such as forming coalitions.we demonstrate applications of this result to several problems. we develop online truthtelling mechanisms for online routing and admission control of path or multicast requests, assuming large network capacities. assuming the existance of an algorithm β for the optimization version of the problem, our techniques provide truthtelling mechanisms for general combinatorial auctions. however, designing optimization algorithms may be difficult in general because of online or approximation lower bounds. for the cases described above, we are able to design optimization algorithms β by amortizing the lost benefit from online computation (and from approximation hardness in the case of multicast) against the benefit obtained from accepted requests.we comment that our upper bounds on profit competitiveness imply, as an obvious corollary, similar bound on global efficiency, namely overall well-being of all the users. this contrasts with most other work on truthtelling mechanisms for general online resource allocation, where only efficiency is maximized, and competitiveness can be arbitrarily poor.
competitive distributed file allocation. this paper deals with the file allocation problem [6] concerning the dynamic optimization of communication costs to access data in a distributed environment. we develop a dynamic file re-allocation strategy that adapts on-line to a sequence of read and write requests whose location and relative frequencies are completely unpredictable. this is achieved by replicating the file in response to read requests and migrating the file in response to write requests while paying the associated communications costs, so as to be closer to processors that access it frequently. we develop first explicit deterministic on-line strategy assuming existence of global information about the state of the network; previous (deterministic) solutions were complicated and more expensive. our solution has (optimal) logarithmic competitive ratio. the paper also contains the first explicit deterministic data migration [7] algorithm achieving the best known competitive ratio for this problem. using somewhat different technique, we also develop the first deterministic distributed file allocation algorithm (using only local information) with poly-logarithmic competitive ratio against a globally optimized optimal prescient strategy.
finding euler circuits in logarithmic parallel time a parallel algorithm for finding euler circuits in graphs is presented. its depth is log |e| and it employs |e| processors. the computational model considered is the pram (the shared memory model). this algorithm is a nice example of utilizing another parallel algorithm that does not seem to be closely related to our problem, namely the algorithm for finding the connected components and a spanning forest of an undirected graph.
adaptive routing with end-to-end feedback: distributed learning and geometric approaches. minimal delay routing is a fundamental task in networks. since delays depend on the (potentially unpredictable) traffic distribution, online delay optimization can be quite challenging. while uncertainty about the current network delays may make the current routing choices sub-optimal, the algorithm can nevertheless try to learn the traffic patterns and keep adapting its choice of routing paths so as to perform nearly as well as the best static path. this online shortest path problem is a special case of online linear optimization, a problem in which an online algorithm must choose, in each round, a strategy from some compact set s ⊆ rd so as to try to minimize a linear cost function which is only revealed at the end of the round. kalai and vempala[4] gave an algorithm for such problems in the transparent feedback model, where the entire cost function is revealed at the end of the round. here we present an algorithm for online linear optimization in the more challenging opaque feedback model, in which only the cost of the chosen strategy is revealed at the end of the round. in the special case of shortest paths, opaque feedback corresponds to the notion that in each round the algorithm learns only the end-to-end cost of the chosen path, not the cost of every edge in the network.we also present a second algorithm for online shortest paths, which solves the shortest-path problem using a chain of online decision oracles, one at each node of the graph. this has several advantages over the online linear optimization approach. first, it is effective against an adaptive adversary, whereas our linear optimization algorithm assumes an oblivious adversary. second, even in the case of an oblivious adversary, the second algorithm performs better than the first, as measured by their additive regret.
competitive distributed job scheduling (extended abstract) this paper examines the problem of balancing the job load in a network of processors, and introduces an online algorithm for scheduling a sequence of jobs in a competitive manner. the algorithm is shown to be polylog (n)-competitive according to a strict definition that forces the online algorithm to be competitive even when considering any bounded area of the network and bounded period of time. we also analyze the common greedy feedback-based approach, and provide matching lower and upper bounds (up to a polylogarithmic factor) for the tradeoff between the costs of searches and updates under this approach.
adapting to asynchronous dynamic networks (extended abstract) the computational power of different communication models is a fundamental question in the theory of distributed computation. for example, in the synchronous model messages are assumed to be delivered within one time unit, whereas in the asynchronous model message delays may be arbitrary. another important parameter of the model is the assumptions about the topology. in the dynamic topology model, links are assumed to crash and recover dynamically, but their status is known to the incident node processors. a meaningful computation can be carried out if the topology stabilizes for a sufficiently long period. in this paper we show that the model of asynchronous, dynamic-topology network is equivalent, up to polylogarithmic factors, to the synchronous, static protocols that can withstand arbitrary link delays and changing topology at the expense of only polylogarithmic blowup in the running time, the number of messages, and the space requirement. previous methods entailed a linear blowup in at least one of these resources. the generality of our method is demonstrated by a series of improvements for important applications, including breadth first search, computing compact efficient routing tables, and packet routing on asynchronous networks.
biased random walks how much can an imperfect source of randomness affect an algorithm? we examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. in our setup, each step of the random walk a &ldquo;controller&rdquo; can, with a certain small probability, fix the next step, thus introducing a bias. we analyze the extent to which the bias can affect the limit behavior of the walk. the controller is assumed to associate a real, nonnegative, &ldquo;benefit&rdquo; with each state, and to strive to maximize the long-term expected benefit. we derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.
balanced allocations (extended abstract). suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. it is well known that when we are done, the fullest box has with high probability lnn/lnlnn(1 + o(1)) balls in it. suppose instead, that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. we show that with high probability, the fullest box contains only lnlnn/ln2 + o(1) balls - exponentially less than before. furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. we discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.
optimal oblivious routing in polynomial time. a recent seminal result of räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. unfortunately, räcke's construction is not polynomial time. we give a polynomial time construction that guarantees räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.
convex programming for scheduling unrelated parallel machines. we consider the classical problem of scheduling parallel unrelated machines. each job is to be processed by exactly one machine. processing job j on machine i requires time pij. the goal is to find a schedule that minimizes the lp norm. previous work showed a 2-approximation algorithm for the problem with respect to the l∞ norm. for any fixed lp norm the previously known approximation algorithm has a performance of θ(p). we provide a 2-approximation algorithm for any fixed lp norm (p>1). this algorithm uses convex programming relaxation. we also give a √ 2-approximation algorithm for the l2 norm. this algorithm relies on convex quadratic programming relaxation. to the best of our knowledge, this is the first time that general convex programming techniques (apart from sdps and cqps) are used in the area of scheduling. we show for any given lp norm a ptas for any fixed number of machines. we also consider the multidimensional generalization of the problem in which the jobs are d-dimensional. here the goal is to minimize the lp norm of the generalized load vector, which is a matrix where the rows represent the machines and the columns represent the jobs dimension. for this problem we give a (d+1)-approximation algorithm for any fixed lp norm (p>1).
spectral analysis of data. experimental evidence suggests that spectral techniques are valuable for a wide range of applications. a partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. in this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. these results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.
management of multi-queue switches in qos networks. the concept of quality of service (qos) networks has gained growing attention recently, as the traffic volume in the internet constantly increases, and qos guarantees are essential to ensure proper operation of most communication based applications. a qos switch serves m incoming queues by transmitting packets arriving at these queues through one output port, one packet per time unit. each packet is marked with a value indicating its guaranteed quality of service. since the queues have bounded capacity and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. the goal is to maximize the total value of transmitted packets. this problem encapsulates two dependent questions: admission control, namely which packets to discard in case of queue overflow, and scheduling, i.e. which queue to use for transmission in each time unit. we use competitive analysis to study online switch performance in qos based networks. specifically, we provide a novel generic technique that decouples the admission control and scheduling problems. our technique transforms any single queue admission control strategy (preemptive or nonpreemptive) to a scheduling and admission control algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given admission control strategy. we use our technique to derive concrete algorithms for the general preemptive and nonpreemptive cases, as well as for the interesting special cases of the 2-value model and the unit value model. to the best of our knowledge this is the first result combining both scheduling and admission control decisions for arbitrary packets sequences in multi-queue switches. we also provide a 1.58-competitive randomized algorithm for the unit value case. this case is interesting by itself since most current networks (e.g. ip networks) only support a best-effort service in which all packets streams are treated equally.
the zero-one principle for switching networks. recently, approximation analysis has been extensively used to study algorithms for routing weighted packets in various network settings. although different techniques were applied in the analysis of diverse models, one common property was evident: the analysis of input sequences composed solely of two different values is always substantially easier, and many results are known only for restricted value sequences. motivated by this, we introduce our zero-one principle for switching networks which characterizes a wide range of algorithms for which achieving c-approximation (as well as c-competitiveness) with respect to sequences composed of 0's and 1's implies achieving c-approximation. the zero-one principle proves to be very efficient in the design of switching algorithms, and substantially facilitates their analysis. we present three applications. first, we consider the multi-queue qos switching model and design a 3-competitive algorithm, improving the result from [6]. second, we study the weighted dynamic routing problem on a line topology of length k and present a (k+1)-competitive algorithm, which improves and generalizes the results from [1,12]. as a third application, we consider the work of [11], that compares the performance of local algorithms to the global optimum in various network topologies, and generalize their results from 2-value sequences to arbitrary value sequences.
trading group theory for randomness in a previous paper [bs] we proved, using the elements of the theory of nilpotent groups, that some of the fundamental computational problems in matriz groups belong to np. these problems were also shown to belong to conp, assuming an unproven hypothesis concerning finite simple groups. the aim of this paper is to replace most of the (proven and unproven) group theory of [bs] by elementary combinatorial arguments. the result we prove is that relative to a random oracle b, the mentioned matrix group problems belong to (np&cap;conp)b. the problems we consider are membership in and order of a matrix group given by a list of generators. these problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. hence np&cap;conp might be the lowest natural complexity class they may fit in. we remark that the results remain valid for black box groups where group operations are performed by an oracle. the tools we introduce seem interesting in their own right. we define a new hierarchy of complexity classes am(k) &ldquo;just above np&rdquo;, introducing arthur vs. merlin games, the bounded-away version of papdimitriou's games against nature. we prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to am=am(2). using a combinatorial lemma on finite groups [be], we construct a game by which the nondeterministic player (merlin) is able to convince the random player (arthur) about the relation [g]=n provided arthur trusts conclusions based on statistical evidence (such as a slowly-strassen type &ldquo;proof&rdquo; of primality). one can prove that am consists precisely of those languages which belong to npb for almost every oracle b. our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the user vs. expert games of goldwasser, micali and rackoff.
isomorphism of graphs with bounded eigenvalue multiplicity we investigate the connection between the spectrum of a graph, i.e. the eigenvalues of the adjacency matrix, and the complexity of testing isomorphism. in particular we describe two polynomial time algorithms which test isomorphism of undirected graphs whose eigenvalues have bounded multiplicity. if x and y are graphs of eigenvalue multiplicity m, then the isomorphism of x and y can be tested by an o(n4m+c) deterministic and by an o(n2m+c) las vegas algorithm, where n is the number of vertices of x and y.
canonical labeling of graphs we announce an algebraic approach to the problem of assigning canonical forms to graphs. we compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n&frac12; + &ogr;(1)),time for general graphs, in subexponential, nlog n, time for tournaments and for 2-(&ngr;,&kgr;,&lgr;) block designs with &kgr;,&lgr; bounded and nlog log n time for &lgr;-planes (symmetric designs) with &lgr; bounded. we prove some related problems np-hard and indicate some open problems.
permutation groups in nc we show that the basic problems of permutation group manipulation admit efficient parallel solutions. given a permutation group g by a list of generators, we find a set of nc-efficient strong generators in nc. using this, we show, that the following problems are in nc: membership in g; determining the order of g; finding the center of g; finding a composition series of g along with permutation representations of each composition factor. moreover, given g, we are able to find the pointwise stabilizer of a set in nc. one consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in nc. the analysis of the algorithms depends, in several ways, on consequences of the classification of finite simple groups.
fast algorithms under the extended riemann hypothesis: a concrete estimate several results in theoretical computer science use the following theorem: for a positive integer q, let z-&-bull;q denote the multiplicative group of all integers x, 0-&-lt;x-&-lt;q, that are relatively prime to q. let g be a proper subgroup of z-&-bull;q. then, assuming the extended riemann hypothesis, there is a constant c such that if q is sufficiently large, z-&-bull;q-&-minus;g contains a positive integer n-&-le;c (logeq)2. we show that for q-&-ge;106, one may take c-&-equil;60. as an application, we discuss a deterministic polynomial-time primality test. miller proved that such algorithms must exist if the erh is true, but we are unable to specify one without the concrete information given above. we eliminate this difficulty, and show how to implement a fast primality test.