Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Comparison of classification ability of hyperball algorithms to neural network and k-nearest neighbour algorithms

The main focus of this thesis is to evaluate and compare Hyperbalilearning algorithm (HBL) to other learning algorithms. In this work HBL is compared to feed forward artificial neural networks using back propagation learning, K-nearest neighbor and 103 algorithms. In order to evaluate the similarity of these algorithms, we carried out three experiments using nine benchmark data sets from UCI machine learning repository. The first experiment compares HBL to other algorithms when sample size of dataset is changing. The second experiment compares HBL to other algorithms when dimensionality of data changes. The last experiment compares HBL to other algorithms according to the level of agreement to data target values. Our observations in general showed, considering classification accuracy as a measure, HBL is performing as good as most ANn variants. Additionally, we also deduced that HBL.:s classification accuracy outperforms 103's and K-nearest neighbour's for the selected data sets.

Verification and FPGA circuits of a block-2 fast path-based predictor

This paper formally derives a new path-based neural branch prediction algorithm (FPP) into blocks of size two for a lower hardware solution while maintaining similar input-output characteristic to the algorithm. The blocked solution, here referred to as B2P algorithm, is obtained using graph theory and retiming methods. Verification approaches were exercised to show that prediction performances obtained from the FPP and B2P algorithms differ within one mis-prediction per thousand instructions using a known framework for branch prediction evaluation. For a chosen FPGA device, circuits generated from the B2P algorithm showed average area savings of over 25% against circuits for the FPP algorithm with similar time performances thus making the proposed blocked predictor superior from a practical viewpoint.

Computer generation and quantitative morphometric analysis of virtual neurons

An important goal in computational neuroanatomy is the complete and accurate simulation of neuronal morphology. We are developing computational tools to model three-dimensional dendritic structures based on sets of stochastic rules. This paper reports an extensive, quantitative anatomical characterization of simulated motoneurons and Purkinje cells. We used several local and global algorithms implemented in the L-Neuron and ArborVitae programs to generate sets of virtual neurons. Parameters statistics for all algorithms were measured from experimental data, thus providing a compact and consistent description of these morphological classes. We compared the emergent anatomical features of each group of virtual neurons with those of the experimental database in order to gain insights on the plausibility of the model assumptions, potential improvements to the algorithms, and non-trivial relations among morphological parameters. Algorithms mainly based on local constraints (e.g., branch diameter) were successful in reproducing many morphological properties of both motoneurons and Purkinje cells (e.g. total length, asymmetry, number of bifurcations). The addition of global constraints (e.g., trophic factors) improved the angle-dependent emergent characteristics (average Euclidean distance from the soma to the dendritic terminations, dendritic spread). Virtual neurons systematically displayed greater anatomical variability than real cells, suggesting the need for additional constraints in the models. For several emergent anatomical properties, a specific algorithm reproduced the experimental statistics better than the others did. However, relative performances were often reversed for different anatomical properties and/or morphological classes. Thus, combining the strengths of alternative generative models could lead to comprehensive algorithms for the complete and accurate simulation of dendritic morphology.

Bound states of bosons and fermions in a mixed vector-scalar coupling with unequal shapes for the potentials

The Klein - Gordon and the Dirac equations with vector and scalar potentials are investigated under a more general condition, V(v) + V(s) = constant. These intrinsically relativistic and isospectral problems are solved in the case of squared hyperbolic potential functions and bound states for either particles or antiparticles are found. The eigenvalues and eigenfuntions are discussed in some detail and the effective Compton wavelength is revealed to be an important physical quantity. It is revealed that a boson is better localized than a fermion when they have the same mass and are subjected to the same potentials.

Branch formation in Pulvinularia suecica (Nostocales, Cyanoprokaryota) and considerations on the classification of dichotomously and pseudodichotomously branched genera

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Application of evolutionary algorithms and the boundary element method in the optimization of noise barrier profiles

[EN]This Ph.D. thesis presents a general, robust methodology that may cover any type of 2D acoustic optimization problem. A procedure involving the coupling of Boundary Elements (BE) and Evolutionary Algorithms is proposed for systematic geometric modifications of road barriers that lead to designs with ever-increasing screening performance. Numerical simulations involving single- and multi-objective optimizations of noise barriers of varied nature are included in this document. results disclosed justify the implementation of this methodology by leading to optimal solutions of previously defined topologies that, in general, greatly outperform the acoustic efficiency of classical, widely used barrier designs normally erected near roads.

Topologically correct intersection curves of tori and natural quadrics

This thesis provides efficient and robust algorithms for the computation of the intersection curve between a torus and a simple surface (e.g. a plane, a natural quadric or another torus), based on algebraic and numeric methods. The algebraic part includes the classification of the topological type of the intersection curve and the detection of degenerate situations like embedded conic sections and singularities. Moreover, reference points for each connected intersection curve component are determined. The required computations are realised efficiently by solving quartic polynomials at most and exactly by using exact arithmetic. The numeric part includes algorithms for the tracing of each intersection curve component, starting from the previously computed reference points. Using interval arithmetic, accidental incorrectness like jumping between branches or the skipping of parts are prevented. Furthermore, the environments of singularities are correctly treated. Our algorithms are complete in the sense that any kind of input can be handled including degenerate and singular configurations. They are verified, since the results are topologically correct and approximate the real intersection curve up to any arbitrary given error bound. The algorithms are robust, since no human intervention is required and they are efficient in the way that the treatment of algebraic equations of high degree is avoided.

UWB radar sensor networks: Detection algorithms design and experimental analysis

In the last years radar sensor networks for localization and tracking in indoor environment have generated more and more interest, especially for anti-intrusion security systems. These networks often use Ultra Wide Band (UWB) technology, which consists in sending very short (few nanoseconds) impulse signals. This approach guarantees high resolution and accuracy and also other advantages such as low price, low power consumption and narrow-band interference (jamming) robustness. In this thesis the overall data processing (done in MATLAB environment) is discussed, starting from experimental measures from sensor devices, ending with the 2D visualization of targets movements over time and focusing mainly on detection and localization algorithms. Moreover, two different scenarios and both single and multiple target tracking are analyzed.

Delayed coverage in malapposed and side-branch struts with respect to well-apposed struts in drug-eluting stents: in vivo assessment with optical coherence tomography

Background—Pathology studies on fatal cases of very late stent thrombosis have described incomplete neointimal coverage as common substrate, in some cases appearing at side-branch struts. Intravascular ultrasound studies have described the association between incomplete stent apposition (ISA) and stent thrombosis, but the mechanism explaining this association remains unclear. Whether the neointimal coverage of nonapposed side-branch and ISA struts is delayed with respect to well-apposed struts is unknown. Methods and Results—Optical coherence tomography studies from 178 stents implanted in 99 patients from 2 randomized trials were analyzed at 9 to 13 months of follow-up. The sample included 38 sirolimus-eluting, 33 biolimus-eluting, 57 everolimus-eluting, and 50 zotarolimus-eluting stents. Optical coherence tomography coverage of nonapposed side-branch and ISA struts was compared with well-apposed struts of the same stent by statistical pooled analysis with a random-effects model. A total of 34 120 struts were analyzed. The risk ratio of delayed coverage was 9.00 (95% confidence interval, 6.58 to 12.32) for nonapposed side-branch versus well-apposed struts, 9.10 (95% confidence interval, 7.34 to 11.28) for ISA versus well-apposed struts, and 1.73 (95% confidence interval, 1.34 to 2.23) for ISA versus nonapposed side-branch struts. Heterogeneity of the effect was observed in the comparison of ISA versus well-apposed struts (H=1.27; I2=38.40) but not in the other comparisons. Conclusions—Coverage of ISA and nonapposed side-branch struts is delayed with respect to well-apposed struts in drug-eluting stents, as assessed by optical coherence tomography.

New Algorithms for M-Estimation of Multivariate Scatter and Location

We present new algorithms for M-estimators of multivariate scatter and location and for symmetrized M-estimators of multivariate scatter. The new algorithms are considerably faster than currently used fixed-point and related algorithms. The main idea is to utilize a second order Taylor expansion of the target functional and to devise a partial Newton-Raphson procedure. In connection with symmetrized M-estimators we work with incomplete U-statistics to accelerate our procedures initially.

Mesozooplankton size data from the fjord branch Kapisigdlit located in the Godthaabsfjord system, West Greenland, 2010

Sampling was conducted from March 24 to August 5 2010, in the fjord branch Kapisigdlit located in the inner part of the Godthåbsfjord system, West Greenland. The vessel "Lille Masik" was used during all cruises except on June 17-18 where sampling was done from RV Dana (National Institute for Aquatic Resources, Denmark). A total of 15 cruises (of 1-2 days duration) 7-10 days apart was carried out along a transect composed of 6 stations (St.), spanning the length of the 26 km long fjord branch. St. 1 was located at the mouth of the fjord branch and St. 6 was located at the end of the fjord branch, in the middle of a shallower inner creek . St. 1-4 was covering deeper parts of the fjord, and St. 5 was located on the slope leading up to the shallow inner creek. Mesozooplankton was sampled by vertical net tows using a Hydrobios Multinet (type Mini) equipped with a flow meter and 50 µm mesh nets or a WP-2 net 50 µm mesh size equipped with a non-filtering cod-end. Sampling was conducted at various times of day at the different stations. The nets were hauled with a speed of 0.2-0.3 m s**-1 from 100, 75 and 50 m depth to the surface at St. 2 + 4, 5 and 6, respectively. The content was immediately preserved in buffered formalin (4% final concentration). All samples were analyzed in the Plankton sorting and identification center in Szczecin (www.nmfri.gdynia.pl). Samples containing high numbers of zooplankton were split into subsamples. All copepods and other zooplankton were identified down to lowest possible taxonomic level (approx. 400 per sample), length measured and counted. Copepods were sorted into development stages (nauplii stage 1 - copepodite stage 6) using morphological features and sizes, and up to 10 individuals of each stage was length measured.