排序方式: 共有58条查询结果,搜索用时 14 毫秒
1.
Miklos Ajtai James Aspnes Moni Naor Yuval Rabani Leonard J Schulman Orli Waarts 《Journal of Algorithms in Cognition, Informatics and Logic》1998,29(2):306-357
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long-lived processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion ofdesiredload of a process, which is a function of the tasks it participates in. Theunfairnessof a system is the maximum, taken over all processes, of the difference between the desired load and the actual load.An example of such a setting is thecarpool problemsuggested by Fagin and Williams [IBM Journal of Research and Development27(2) (1983), 133–139]. In this problem, a set ofnpeople form a carpool. On each day a subset of the people arrive and one of them is designated as the driver. A scheduling rule is required so that the driver will be determined in a “fair” way.We investigate this problem under various assumptions on the input distribution. We also show that the carpool problems can capture several other problems of fairness in scheduling. 相似文献
2.
3.
It is shown that for every \(p\in (2,\infty )\) there exists a doubling subset of \(L_p\) that does not admit a bi-Lipschitz embedding into \(\mathbb R^k\) for any \(k\in \mathbb N\) . 相似文献
4.
This paper is concerned with a new version of on-line storage allocation in which the durations of all processes are known at their arrival time. This version of the problem is motivated by applications in communication networks and has not been studied previously. We provide an on-line algorithm for the problem with a competitive ratio of O(min{log Δ,log τ}), where Δ is the ratio between the longest and shortest duration of a process, and τ is the maximum number of concurrent active processes that have different durations. For the special case where all durations are powers of two, the competitive ratio achieved is O(loglog Δ). 相似文献
5.
We prove that for every n ∈ ? there exists a metric space (X, d X), an n-point subset S ? X, a Banach space (Z, \({\left\| \right\|_Z}\)) and a 1-Lipschitz function f: S → Z such that the Lipschitz constant of every function F: X → Z that extends f is at least a constant multiple of \(\sqrt {\log n} \). This improves a bound of Johnson and Lindenstrauss [JL84]. We also obtain the following quantitative counterpart to a classical extension theorem of Minty [Min70]. For every α ∈ (1/2, 1] and n ∈ ? there exists a metric space (X, d X), an n-point subset S ? X and a function f: S → ?2 that is α-Hölder with constant 1, yet the α-Hölder constant of any F: X → ?2 that extends f satisfies \({\left\| F \right\|_{Lip\left( \alpha \right)}} > {\left( {\log n} \right)^{\frac{{2\alpha - 1}}{{4\alpha }}}} + {\left( {\frac{{\log n}}{{\log \log n}}} \right)^{{\alpha ^2} - \frac{1}{2}}}\). We formulate a conjecture whose positive solution would strengthen Ball’s nonlinear Maurey extension theorem [Bal92], serving as a far-reaching nonlinear version of a theorem of König, Retherford and Tomczak-Jaegermann [KRTJ80]. We explain how this conjecture would imply as special cases answers to longstanding open questions of Johnson and Lindenstrauss [JL84] and Kalton [Kal04]. 相似文献
6.
Dorit S. Hochbaum Nimrod Megiddo Joseph Naor Arie Tamir 《Mathematical Programming》1993,62(1-3):69-83
The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU
2 log(Un
2
m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ. 相似文献
7.
A single-server queueing system with constant Poisson input is considered and the partial elimination of the station's idle fraction is envisaged by intermittent close-down and set-up. The rule pertaining to the dismantling and re-establishing of the service station—the management doctrine—is based on the instantaneous size of the queue, but these processes are assumed to consume time. Operating characteristics of such systems—in particular, average queue length and queueing time—are evaluated. A cost structure is superimposed on the system and optimization procedures are outlined. The close relationship with (a) priority queueing and (b) storage models is pointed out. 相似文献
8.
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability measure. This
provides a refined and unified framework for the two primary methods of constructing Fréchet embeddings for finite metrics,
due to Bourgain (1985) and Rao (1999). We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion
where αX is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an
distortion embedding, where λX is the doubling constant of X. Since λX ≤ n, this result recovers Bourgain’s theorem, but when the metric X is, in a sense, “low-dimensional,” improved bounds are achieved.
Our embeddings are volume-respecting for subsets of arbitrary size. One consequence is the existence of (k, O(log n)) volume-respecting embeddings for all 1 ≤ k ≤ n, which is the best possible, and answers positively a question posed by U. Feige. Our techniques are also used to answer
positively a question of Y. Rabinovich, showing that any weighted n-point planar graph embeds in
with O(1) distortion. The O(log n) bound on the dimension is optimal, and improves upon the previously known bound of O((log n)2).
Received: April 2004 Accepted: August 2004 Revision: December 2004
J.R.L. Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship. 相似文献
9.
It is shown that the edges of any n-point vertex expander can be replaced by new edges so that the resulting graph is an edge expander, and such that any two vertices that are joined by a new edge are at distance in the original graph. This result is optimal, and is shown to have various geometric consequences. In particular, it is used to obtain an alternative perspective on the recent algorithm of Arora et al. [Proceedings of the 36th Annual ACM Symposium on the Theory of Computing, 2004, pp. 222-231.] for approximating the edge expansion of a graph, and to give a nearly optimal lower bound on the ratio between the observable diameter and the diameter of doubling metric measure spaces which are quasisymmetrically embeddable in Hilbert space. 相似文献
10.
We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is D-equivalent to an ultrametric, where D ∈ (2,∞) is a prescribed target distortion. Since this procedure works for D arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of [3], answering a question from [12], and yielding the best known bounds in the nonlinear Dvoretzky theorem. Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a “scale-oblivious” fragmentation procedure. 相似文献