Fairness in Scheduling

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.     

Current development of analytical affinity chromatography: Design and biotechnological uses of molecular recognition surfaces

Analytical high performance liquid affinity chromatography (analytical HPLAC) has been investigated as an experimental guide to both synthetic design and affinity technological use of peptide and protein recognition surfaces. This work has progressed from the ongoing use of analytical affinity chromatography to study interaction mechanisms of naturally-occurring peptides and proteins, including enzyme fragment complexes and neuroendocrine biosynthetic precursors. We recently initiated a study to use analytical HPLAC for de novo design of recognition peptides called “anti-sense peptides”. Present data suggest the potential to use anti-sense peptides as “synthetic antibodies”, in immobilized forms, for biomolecular separation and analysis. Analogous studies have been started with immobilized natural antibodies in analytical immuno HPLAC. Our present data typify the growing usefulness of analytical HPLAC when designing recognition molecules, analyzing their interaction characteristics, and devising ways to use them in affinity technology.     

A doubling subset of L_p for p>2 that is inherently infinite dimensional

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\) .     

Dynamic storage allocation with known durations

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 Δ).     

On Lipschitz extension from finite subsets

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 → ?₂ that is α-Hölder with constant 1, yet the α-Hölder constant of any F: X → ?₂ 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].     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

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 ² log(Un ² 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.     

Queueing Systems with a Removable Service Station

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.     

Measured descent: a new embedding method for finite metrics

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)²). Received: April 2004 Accepted: August 2004 Revision: December 2004 J.R.L. Supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship.     

Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs

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.