To see the other types of publications on this topic, follow the link: Online algorithms with recourse.
Dissertations / Theses on the topic 'Online algorithms with recourse'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Online algorithms with recourse.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Lowe, Wing Wah. "An exploration of stochastic decomposition algorithms for stochastic linear programs with recourse." Diss., The University of Arizona, 1994. http://hdl.handle.net/10150/186667.
Full textAbstract:
Stochastic linear programs are linear programs in which some of the problem data are random variables. The particular kind of programs that we study belong to the recourse model. Under this model, some decisions are postponed until better information becomes available (e.g., an outcome of a random variable is realized), while other decisions must be made 'here and now.' For example, in a telecommunication network planning problem, decisions regarding the addition of network capacity have to be made before knowing customer demand (i.e., 'here and now'). Once the demand is realized, efficient usage of the network can then be determined. This work explores algorithms for the solution of such programs: stochastic linear programs with recourse. The algorithms investigated can be described as decomposition based cutting plane methods in which the cuts are estimated from random samples. Moreover, the algorithms all use the incremental sampling plan inherent to the Stochastic Decomposition (SD) algorithm developed by Higle and Sen in 1991. Our study includes both two stage and multistage programs. For the solution of two stage programs, we present the Conditional Stochastic Decomposition (CSD) algorithm, a multicut version of the SD algorithm. CSD is most suitable for situations in which data are difficult to obtain and may be computationally intense. Because of this potential intensity, we explore algorithms which require less computational effort than CSD. These algorithms combine features of both CSD and SD and are referred to as hybrid algorithms. Following our exploration of these algorithms for two stage problems, we next explore an extension of the SD algorithm that can be used for multistage problems with stagewise independent random variables. For the sake of notational brevity, our technical development is centered around the three stage case, although the extension to multistage problems is straightforward. Under mild conditions, convergence results similar to those found in the two stage algorithms hold. Multistage stochastic decomposition is currently a largely uncharted area. Our research represents the first major effort in this direction.
2
Li, Le. "Online stochastic algorithms." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0031.
Full textAbstract:
Cette thèse travaille principalement sur trois sujets. Le premier concentre sur le clustering en ligne dans lequel nous présentons un nouvel algorithme stochastique adaptatif pour regrouper des ensembles de données en ligne. Cet algorithme repose sur l'approche quasi-bayésienne, avec une estimation dynamique (i.e., dépendant du temps) du nombre de clusters. Nous prouvons que cet algorithme atteint une borne de regret de l'ordre et que cette borne est asymptotiquement minimax sous la contrainte sur le nombre de clusters. Nous proposons aussi une implémentation par RJMCMC. Le deuxième sujet est lié à l'apprentissage séquentiel des courbes principales qui cherche à résumer une séquence des données par une courbe continue. Pour ce faire, nous présentons une procédure basée sur une approche maximum a posteriori pour le quasi-posteriori de Gibbs. Nous montrons que la borne de regret de cet algorithme et celui de sa version adaptative est sous-linéaire en l'horizon temporel T. En outre, nous proposons une implémentation par un algorithme glouton local qui intègre des éléments de sleeping experts et de bandit à plusieurs bras. Le troisième concerne les travaux qui visent à accomplir des tâches pratiques au sein d'iAdvize, l'entreprise qui soutient cette thèse. Il inclut l'analyse des sentiments pour les messages textuels et l'implémentation de chatbot dans lesquels la première est réalisé par les méthodes classiques dans la fouille de textes et les statistiques et la seconde repose sur le traitement du langage naturel et les réseaux de neurones artificiels<br>This thesis works mainly on three subjects. The first one is online clustering in which we introduce a new and adaptive stochastic algorithm to cluster online dataset. It relies on a quasi-Bayesian approach, with a dynamic (i.e., time-dependent) estimation of the (unknown and changing) number of clusters. We prove that this algorithm has a regret bound of the order of and is asymptotically minimax under the constraint on the number of clusters. A RJMCMC-flavored implementation is also proposed. The second subject is related to the sequential learning of principal curves which seeks to represent a sequence of data by a continuous polygonal curve. To this aim, we introduce a procedure based on the MAP of Gibbs-posterior that can give polygonal lines whose number of segments can be chosen automatically. We also show that our procedure is supported by regret bounds with sublinear remainder terms. In addition, a greedy local search implementation that incorporates both sleeping experts and multi-armed bandit ingredients is presented. The third one concerns about the work which aims to fulfilling practical tasks within iAdvize, the company which supports this thesis. It includes sentiment analysis for textual messages by using methods in both text mining and statistics, and implementation of chatbot based on nature language processing and neural networks
3
Shi, Tian. "Novel Algorithms for Understanding Online Reviews." Diss., Virginia Tech, 2021. http://hdl.handle.net/10919/104998.
Full textAbstract:
This dissertation focuses on the review understanding problem, which has gained attention from both industry and academia, and has found applications in many downstream tasks, such as recommendation, information retrieval and review summarization. In this dissertation, we aim to develop machine learning and natural language processing tools to understand and learn structured knowledge from unstructured reviews, which can be investigated in three research directions, including understanding review corpora, understanding review documents, and understanding review segments.
For the corpus-level review understanding, we have focused on discovering knowledge from corpora that consist of short texts. Since they have limited contextual information, automatically learning topics from them remains a challenging problem. We propose a semantics-assisted non-negative matrix factorization model to deal with this problem. It effectively incorporates the word-context semantic correlations into the model, where the semantic relationships between the words and their contexts are learned from the skip-gram view of a corpus. We conduct extensive sets of experiments on several short text corpora to demonstrate the proposed model can discover meaningful and coherent topics.
For document-level review understanding, we have focused on building interpretable and reliable models for the document-level multi-aspect sentiment analysis (DMSA) task, which can help us to not only recover missing aspect-level ratings and analyze sentiment of customers, but also detect aspect and opinion terms from reviews. We conduct three studies in this research direction. In the first study, we collect a new DMSA dataset in the healthcare domain and systematically investigate reviews in this dataset, including a comprehensive statistical analysis and topic modeling to discover aspects. We also propose a multi-task learning framework with self-attention networks to predict sentiment and ratings for given aspects. In the second study, we propose corpus-level and concept-based explanation methods to interpret attention-based deep learning models for text classification, including sentiment classification. The proposed corpus-level explanation approach aims to capture causal relationships between keywords and model predictions via learning importance of keywords for predicted labels across a training corpus based on attention weights. We also propose a concept-based explanation method that can automatically learn higher level concepts and their importance to model predictions. We apply these methods to the classification task and show that they are powerful in extracting semantically meaningful keywords and concepts, and explaining model predictions. In the third study, we propose an interpretable and uncertainty aware multi-task learning framework for DMSA, which can achieve competitive performance while also being able to interpret the predictions made. Based on the corpus-level explanation method, we propose an attention-driven keywords ranking method, which can automatically discover aspect terms and aspect-level opinion terms from a review corpus using the attention weights. In addition, we propose a lecture-audience strategy to estimate model uncertainty in the context of multi-task learning.
For the segment-level review understanding, we have focused on the unsupervised aspect detection task, which aims to automatically extract interpretable aspects and identify aspect-specific segments from online reviews. The existing deep learning-based topic models suffer from several problems such as extracting noisy aspects and poorly mapping aspects discovered by models to the aspects of interest. To deal with these problems, we propose a self-supervised contrastive learning framework in order to learn better representations for aspects and review segments. We also introduce a high-resolution selective mapping method to efficiently assign aspects discovered by the model to the aspects of interest. In addition, we propose using a knowledge distillation technique to further improve the aspect detection performance.<br>Doctor of Philosophy<br>Nowadays, online reviews are playing an important role in our daily lives. They are also critical to the success of many e-commerce and local businesses because they can help people build trust in brands and businesses, provide insights into products and services, and improve consumers' confidence. As a large number of reviews accumulate every day, a central research problem is to build an artificial intelligence system that can understand and interact with these reviews, and further use them to offer customers better support and services. In order to tackle challenges in these applications, we first have to get an in-depth understanding of online reviews.
In this dissertation, we focus on the review understanding problem and develop machine learning and natural language processing tools to understand reviews and learn structured knowledge from unstructured reviews. We have addressed the review understanding problem in three directions, including understanding a collection of reviews, understanding a single review, and understanding a piece of a review segment. In the first direction, we proposed a short-text topic modeling method to extract topics from review corpora that consist of primary complaints of consumers. In the second direction, we focused on building sentiment analysis models to predict the opinions of consumers from their reviews. Our deep learning models can provide good prediction accuracy as well as a human-understandable explanation for the prediction. In the third direction, we develop an aspect detection method to automatically extract sentences that mention certain features consumers are interested in, from reviews, which can help customers efficiently navigate through reviews and help businesses identify the advantages and disadvantages of their products.
4
Trippen, Gerhard Wolfgang. "Online exploration and search in graphs /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?COMP%202006%20TRIPPE.
Full text
5
Li, Rongbin, and 李榕滨. "New competitive algorithms for online job scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197555.
Full textAbstract:
Job scheduling, which greatly impacts on the system performance, is a fundamental problem in computer science. In this thesis, we study three kinds of scheduling problems, that is, deadline scheduling, due date scheduling, and flow time scheduling. Traditionally, the major concern for scheduling problems is the system performance, i.e. the “Quality of Service" (QoS). Different scheduling problems use different QoS measurements. For deadline scheduling, the most common QoS to optimize is the throughput; for due date scheduling, it is the total quoted lead time; and for flow time scheduling, it is the total (weighted) flow time.
Recently, energy efficiency is becoming more and more important. Many modern processors adopt technologies like dynamic speed scaling and sleep management to reduce energy usage. Much work is done on energy efficient scheduling. In this thesis, we study this topic for all three kinds of scheduling mentioned above.
Meanwhile, we also revisit the traditional flow time scheduling problem to optimize the QoS. However, we consider the problem in a more realistic model that makes the problem much more challenging.
Below is the summary of the problems studied in the thesis. First, we consider the tradeoff between energy and throughput for deadline scheduling. Specifically, each job is associated with a value (or importance) and a deadline. A scheduling algorithm is allowed to discard some of the jobs, and the objective is to minimize total energy usage plus total value of discarded jobs. When processor's maximum speed is unbounded, we propose an O(1)-competitive algorithm. When processor's maximum speed is bounded, we show a strong lower bound and give an algorithm with a competitive ratio close to that lower bound.
Second, we study energy efficient due date scheduling. Jobs arrive online with different sizes and weights. An algorithm needs to assign a due date to each job once it arrives, and complete the job by the due date. The quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We propose a competitive algorithm for minimizing the sum of the total quoted lead time and energy usage.
Next, we consider flow time scheduling with power management on multiple machines. Jobs with arbitrary sizes and weights arrive online. Each machine consumes different amount of energy when processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage and, meanwhile, guarantee high QoS. Our result is an O(1)-competitive algorithm to minimize total weighted flow time plus energy usage.
Finally, we consider the traditional preemptive scheduling to minimize total flow time. Previous theoretical results often assume preemption is free, which is not true for most systems. We investigate the complexity of the problem when a processor has to perform a certain amount of overhead before it resumes the execution of a job preempted before. We first show an Ω(n^(1/4)) lower bound, and then, propose a (1+ε)-speed (1+ 1/ε )-competitive algorithm in resource augmentation model.<br>published_or_final_version<br>Computer Science<br>Doctoral<br>Doctor of Philosophy
6
ALBUQUERQUE, LUIZ FERNANDO FERNANDES DE. "ONLINE ALGORITHMS ANALYSIS FOR SPONSORED LINKS SELECTION." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2009. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=16088@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>Links patrocinados são aqueles que aparecem em destaque nos resultados de
pesquisas em máquinas de busca na Internet e são grande fonte de receita
para seus provedores. Para os anunciantes, que fazem ofertas por palavras-chave
para aparecerem em destaque nas consultas dos usuários, são uma
oportunidade de divulgação da marca, conquista e manutenção de clientes.
Um dos desafios das máquinas de busca neste modelo de negócio é selecionar
os anunciantes que serão exibidos a cada consulta de modo a maximizar sua
receita em determinado período. Este é um problema tipicamente online,
onde a cada consulta é tomada uma decisão sem o conhecimento prévio
das próximas consultas. Após uma decisão ser tomada, esta não pode mais
ser alterada. Nesta dissertação avaliamos experimentalmente algoritmos
propostos na literatura para solução deste problema, comparando-os à
solução ótima offline, em simulações com dados sintéticos. Supondo que
o conjunto das consultas diárias obedeça a uma determinada distribuição,
propomos dois algoritmos baseados em informações estocásticas que são
avaliados nos mesmos cenários que os outros algoritmos.<br>Sponsored links are those that appear highlighted at Internet search engine
results. They are responsible for a large amount of their providers’ revenue.
To advertisers, that place bids for keywords in large auctions at Internet,
these links are the opportunity of brand exposing and achieving more clients.
To search engine companies, one of the main challenges in this business
model is selecting which advertisers should be allocated to each new query
to maximize their total revenue in the end of the day. This is a typical
online problem, where for each query is taken a decision without previous
knowledge of future queries. Once the decision is taken, it can not be
modified anymore. In this work, using synthetically generated data, we do
experimental evaluation of three algorithms proposed in the literature for
this problem and compare their results with the optimal offline solution.
Considering that daily query set obeys some well known distribution, we
propose two algorithms based on stochastic information, those are evaluated
in the same scenarios of the others.
7
Pasteris, S. U. "Efficient algorithms for online learning over graphs." Thesis, University College London (University of London), 2016. http://discovery.ucl.ac.uk/1516210/.
Full textAbstract:
In this thesis we consider the problem of online learning with labelled graphs, in particular designing algorithms that can perform this problem quickly and with low memory requirements. We consider the tasks of Classification (in which we are asked to predict the labels of vertices) and Similarity Prediction (in which we are asked to predict whether two given vertices have the same label). The first half of the thesis considers non- probabilistic online learning, where there is no probability distribution on the labelling and we bound the number of mistakes of an algorithm by a function of the labelling's complexity (i.e. its "naturalness"), often the cut- size. The second half of the thesis considers probabilistic machine learning in which we have a known probability distribution on the labelling. Before considering probabilistic online learning we first analyse the junction tree algorithm, on which we base our online algorithms, and design a new ver- sion of it, superior to the otherwise current state of the art. Explicitly, the novel contributions of this thesis are as follows: • A new algorithm for online prediction of the labelling of a graph which has better performance than previous algorithms on certain graph and labelling families. • Two algorithms for online similarity prediction on a graph (a novel problem solved in this thesis). One performs very well whilst the other not so well but which runs exponentially faster. • A new (better than before, in terms of time and space complexity) state of the art junction tree algorithm, as well as an application of it to the problem of online learning in an Ising model. • An algorithm that, in linear time, finds the optimal junction tree for online inference in tree-structured Ising models, the resulting online junction tree algorithm being far superior to the previous state of the art. All claims in this thesis are supported by mathematical proofs.
8
Bonifaci, Vincenzo. "Models and algorithms for online server routing." Doctoral thesis, La Sapienza, 2007. http://hdl.handle.net/11573/917056.
Full text
9
Harrington, Edward Francis. "Aspects of online learning /." View thesis entry in Australian Digital Theses Program, 2004. http://thesis.anu.edu.au/public/adt-ANU20060328.160810/index.html.
Full text
10
Kamphans, Thomas. "Models and algorithms for online exploration and search." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980408121.
Full text
11
Birks, Martin David. "Online algorithms for temperature aware job scheduling problems." Thesis, University of Leicester, 2012. http://hdl.handle.net/2381/27686.
Full textAbstract:
Temperature is an important consideration when designing microprocessors. When exposed to high temperatures component reliability can be reduced, while some components completely fail over certain temperatures. We consider the design and analysis of online algorithms; in particular algorithms that use knowledge of the amount of heat a job will generate. We consider algorithms with two main objectives. The first is maximising job throughput. We show upper and lower bounds for the case where jobs are unit length, both when jobs are weighted and unweighted. Many of these bounds are matching for all cooling factors in the single and multiple machine case. We extend this to consider the single machine case where jobs have longer than unit length. When all jobs are equal length we show matching bounds for the case without preemption. We also show that both models of pre-emption enable at most a slight reduction in the competitive ratio of algorithms. We then consider when jobs have variable lengths. We analyse both the models of unweighted jobs and the jobs with weights proportional to their length. We show bounds that match within constant factors, in the non-preemptive and both preemptive models. The second objective we consider is minimising flow time. We consider the objective of minimising the total flow time of a schedule. We show NP-hardness and inapproximability results for the offline case, as well as giving an approximation algorithm for the case where all release times are equal. For the online case we give some negative results for the case where maximum job heats are bounded. We also give some results for a resource augmentation model that include a 1-competitive algorithm when the extra power for the online algorithm is high enough. Finally we consider the objective of minimising the maximum flow time of any job in a schedule.
12
Zadimoghaddam, Morteza. "Online allocation algorithms with applications in computational advertising." Thesis, Massachusetts Institute of Technology, 2014. http://hdl.handle.net/1721.1/87940.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 99-107).<br>Over the last few decades, a wide variety of allocation markets emerged from the Internet and introduced interesting algorithmic challenges, e.g., ad auctions, online dating markets, matching skilled workers to jobs, etc. I focus on the use of allocation algorithms in computational advertising as it is the quintessential application of my research. I will also touch on the classic secretary problem with submodular utility functions, and show that how it is related to advertiser's optimization problem in computational advertising applications. In all these practical situations, we should focus on solving the allocation problems in an online setting since the input is being revealed during the course of the algorithm, and at the same time we should make irrevocable decisions. We can formalize these types of computational advertising problems as follows. We are given a set of online items, arriving one by one, and a set of advertisers where each advertiser specifies how much she wants to pay for each of the online items. The goal is to allocate online items to advertisers to maximize some objective function like the total revenue, or the total quality of the allocation. There are two main classes of extensively studied problems in this context: budgeted allocation (a.k.a. the adwords problem) and display ad problems. Each advertiser is constrained by an overall budget limit, the maximum total amount she can pay in the first class, and by some positive integer capacity, the maximum number of online items we can assign to her in the second class.<br>by Morteza Zadimoghaddam.<br>Ph. D.
13
Packer, Heather S. "Evolving ontologies with online learning and forgetting algorithms." Thesis, University of Southampton, 2011. https://eprints.soton.ac.uk/194923/.
Full textAbstract:
Agents that require vocabularies to complete tasks can be limited by static vocabularies which cannot evolve to meet unforeseen domain tasks, or reflect its changing needs or environment. However, agents can benefit from using evolution algorithms to evolve their vocabularies, namely the ability to support new domain tasks. While an agent can capitalise on being able support more domain tasks, using existing techniques can hinder them because they do not consider the associated costs involved with evolving an agent's ontology. With this motivation, we explore the area of ontology evolution in agent systems, and focus on the reduction of the costs associated with an evolving ontology. In more detail, we consider how an agent can reduce the costs of evolving an ontology, these include costs associated with: the acquisition of new concepts; processing new concepts; the increased memory usage from storing new concepts; and the removal of unnecessary concepts. Previous work reported in the literature has largely failed to analyse these costs in the context of evolving an agent's ontology. Against this background, we investigate and develop algorithms to enable agents to evolve their ontologies. More specifically, we present three online evolution algorithms that enable agents to: i) augment domain related concepts, ii) use prediction to select concepts to learn, and iii) prune unnecessary concepts from their ontology, with the aim to reduce the costs associated with the acquisition, processing and storage of acquired concepts. In order to evaluate our evolution algorithms, we developed an agent framework which enables agents to use these algorithms and measure an agent's performance. Finally, our empirical evaluation shows that our algorithms are successful in reducing the costs associated with evolving an agent's ontology.
14
Moon, Kyung Seob. "Consistency Maintenance Algorithms for Multiplayer Online Digital Games." Thesis, Griffith University, 2007. http://hdl.handle.net/10072/367081.
Full textAbstract:
Multiplayer Online Digital Games (MODIGs) are gaining in popularity because of the strategic sophistication added when games are played against other humans, as opposed to computer artificial intelligence (AI) opponents. However, the actualisation of multiplayer games is not easy, due to their complexity. Multiplayer games are the combined applications of various areas, such as networking, graphics, AI, sound, and process optimisation. Among them, problems related to networking -- such as limitations in data transfer rate, latency, and jitter -- are the most difficult to resolve. Network latency cannot be avoided completely and introduces various problems such as inconsistency of player status, recognisable responsiveness, and irregular network lag.
Generally, the network architectures of MODIGs can be categorized into three groups: Client-Server (C/S), Peer-to-Peer (P2P), and hybrid. In general, MODIG designers prefer the C/S network architecture to the P2P system. The main reason for this is that the C/S model enjoys certain advantages, such as simplicity of consistency maintenance, improved security, efficient authentification, and ease of billing system management. However, the C/S architecture can cause network latency and often servers do become network bottlenecks. To solve this problem, server clustering methods are used, but these solutions may not be cost effective. This is why a number of games use the P2P network architecture, but in this structure the total number of players in any one game session is often limited, because of the network’s bandwidth constraints. In addition, the consistency maintenance issue becomes critical within this architecture.
There are two main approaches for maintaining consistency in MODIGs: conservative and optimistic. The former approach involves a send-and-wait philosophy, requiring acknowledgement frames and resulting in packet transfer delay, such that players may experience network latency. In the latter approach, the processes do not wait for other players' packets and advance to their own frames, thus no network latency occurs. However, when there is inconsistency between players, the processes must roll back to correct mis-ordered operations due to packet transfer delay. These can cause irritation and confusion to players, and thus the quality of game deteriorates. Overall, the optimistic approaches may not be suitable for network games.
To alleviate network latency and reduce bandwidth requirements in conservative consistency maintenance algorithms and the P2P-based approaches, a new system is proposed and designed. To reduce network latency, a conservative consistency maintenance algorithm named Locked Bucket Synchronisation (LBS) is proposed to mask latency and maintain perfect consistency among players. In addition, a distributed network architecture is adopted and a tree-based P2P system is proposed, to remove additional packet transfer delays between server and client. To reduce network latency caused by packet drop and delay, a smart transmission scheme (STS) is proposed. To alleviate the bandwidth problem, a packet aggregation method is introduced. These approaches are thoroughly examined and analysed.
To evaluate the efficiency of the proposed system, a network simulator, COMP2P, and a real network game, Duel-X, are implemented. The efficiency of the proposed consistency algorithm, LBS is compared with that of other approaches such as Lockstep (LS) and Frequent State Regeneration (FSR). The system architectures of COMP2P and Duel-X as well as the results of experiments are fully documented.
The experimental results from COMP2P show that the proposed LBS algorithm outperforms the LS algorithm under all tested circumstances, in terms of game execution speed. The LBS algorithm with the tree-based P2P system achieves almost optimal frame rate under the condition of a 10% packet drop rate, while the LS algorithm with the tree-base P2P system performs at approximately 40% of optimal frame rate.
The efficiency of the Smart Transmission Scheme (STS) with the LBS algorithm is compared with the Blind Transmission Scheme (BTS) and the experimental results indicate that the BTS increases the bandwidth requirement of players by 100% while the STS raises by only 10% the optimal value of the bandwidth requirement without degrading game execution speed significantly.
Finally, the proposed packet aggregation method together with the LBS algorithm reduce by 50% the bandwidth requirement of players, without lowering game execution speed, when compared with the case of using the LBS algorithm only.
To verify and validate the efficiency of the LBS algorithm, various experiments are performed on Duel-X. The experimental results show that the LBS algorithm masks network latency without harming consistency between players. When the LBS algorithm is adopted, the rate of frame interval approaches the optimal values that can be achieved under the FSR algorithm. This implies that the LBS algorithm improves the playability of MODIGs without degrading consistency between players.
The overall experimental results show that actualisation of reliable and robust MODIGs is achievable with a combination of P2P-based architecture and conservative consistency maintenance algorithms.<br>Thesis (PhD Doctorate)<br>Doctor of Philosophy (PhD)<br>School of Information and Communication Technology<br>Faculty of Engineering and Information Technology<br>Full Text
15
Chowuraya, Tawanda. "Online content clustering using variant K-Means Algorithms." Thesis, Cape Peninsula University of Technology, 2019. http://hdl.handle.net/20.500.11838/3089.
Full textAbstract:
Thesis (MTech)--Cape Peninsula University of Technology, 2019<br>We live at a time when so much information is created. Unfortunately, much of the information is redundant. There is a huge amount of online information in the form of news articles that discuss similar stories. The number of articles is projected to grow. The growth makes it difficult for a person to process all that information in order to update themselves on a subject matter. There is an overwhelming amount of similar information on the internet. There is need for a solution that can organize this similar information into specific themes. The solution is a branch of Artificial intelligence (AI) called machine learning (ML) using clustering algorithms. This refers to clustering groups of information that is similar into containers. When the information is clustered people can be presented with information on their subject of interest, grouped together. The information in a group can be further processed into a summary.
This research focuses on unsupervised learning. Literature has it that K-Means is one of the most widely used unsupervised clustering algorithm. K-Means is easy to learn, easy to implement and is also efficient. However, there is a horde of variations of K-Means. The research seeks to find a variant of K-Means that can be used with an acceptable performance, to cluster duplicate or similar news articles into correct semantic groups.
The research is an experiment. News articles were collected from the internet using gocrawler. gocrawler is a program that takes Universal Resource Locators (URLs) as an argument and collects a story from a website pointed to by the URL. The URLs are read from a repository. The stories come riddled with adverts and images from the web page. This is referred to as a dirty text.
The dirty text is sanitized. Sanitization is basically cleaning the collected news articles. This includes removing adverts and images from the web page. The clean text is stored in a repository, it is the input for the algorithm. The other input is the K value. All K-Means based variants take K value that defines the number of clusters to be produced.
The stories are manually classified and labelled. The labelling is done to check the accuracy of machine clustering. Each story is labelled with a class to which it belongs. The data collection process itself was not unsupervised but the algorithms used to cluster are totally unsupervised. A total of 45 stories were collected and 9 manual clusters were identified. Under each manual cluster there are sub clusters of stories talking about one specific event.
The performance of all the variants is compared to see the one with the best clustering results. Performance was checked by comparing the manual classification and the clustering results from the algorithm.
Each K-Means variant is run on the same set of settings and same data set, that is 45 stories. The settings used are, • Dimensionality of the feature vectors,
• Window size,
• Maximum distance between the current and predicted word in a sentence,
• Minimum word frequency,
• Specified range of words to ignore,
• Number of threads to train the model.
• The training algorithm either distributed memory (PV-DM) or distributed bag of words (PV-DBOW),
• The initial learning rate. The learning rate decreases to minimum alpha as training progresses,
• Number of iterations per cycle, • Final learning rate,
• Number of clusters to form,
• The number of times the algorithm will be run,
• The method used for initialization.
The results obtained show that K-Means can perform better than K-Modes. The results are tabulated and presented in graphs in chapter six.
Clustering can be improved by incorporating Named Entity (NER) recognition into the K-Means algorithms. Results can also be improved by implementing multi-stage clustering technique. Where initial clustering is done then you take the cluster group and further cluster it to achieve finer clustering results.
16
Hung, Yee-shing Regant. "Scheduling online batching systems." Click to view the E-thesis via HKUTO, 2005. http://sunzi.lib.hku.hk/hkuto/record/B34624016.
Full text
17
Drapkin, Dimitri [Verfasser], Rüdiger [Akademischer Betreuer] Schultz, and Maarten H. van der [Akademischer Betreuer] Vlerk. "Models and algorithms for dominance-constrained stochastic programs with recourse / Dimitri Drapkin. Gutachter: Maarten H. van der Vlerk. Betreuer: Rüdiger Schultz." Duisburg, 2014. http://d-nb.info/105157966X/34.
Full text
18
Mak, Kin-sum. "Energy efficient online deadline scheduling." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/HKUTO/record/B39558277.
Full text
19
麥健心 and Kin-sum Mak. "Energy efficient online deadline scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B39558277.
Full text
20
CESARI, TOMMASO RENATO. "ALGORITHMS, LEARNING, AND OPTIMIZATION." Doctoral thesis, Università degli Studi di Milano, 2020. http://hdl.handle.net/2434/699354.
Full textAbstract:
This thesis covers some algorithmic aspects of online machine learning and optimization. In Chapter 1 we design algorithms with state-of-the-art regret guarantees for the problem dynamic pricing. In Chapter 2 we move on to an asynchronous online learning setting in which only some of the agents in the network are active at each time step. We show that when information is shared among neighbors, knowledge about the graph structure might have a significantly different impact on learning rates depending on how agents are activated. In Chapter 3 we investigate the online problem of multivariate non-concave maximization under weak assumptions on the regularity of the objective function. In Chapter 4 we introduce a new performance measure and design an efficient algorithm to learn optimal policies in repeated A/B testing.
21
Zhu, Jianqiao, and 朱剑桥. "New results on online job scheduling." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hub.hku.hk/bib/B50662351.
Full textAbstract:
This thesis presents several new results on online job scheduling. Job scheduling is a basic requirement of many practical computer systems, and the scheduling behavior directly affects a system’s performance. In theoretical aspect, scheduling scenarios are abstracted into scheduling models, which are studied mathematically. In this thesis, we look into a variety of scheduling models which are under active research. We incorporate these models and organize them into generalized pictures.
We first study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)-competitive algorithms for this problem under the unit-weight multi-processor setting [13, 14] as well as the weighted single-processor setting [5]. This thesis shows the first O(1)-competitive algorithm for weighted flow time in the multi-processor setting.
In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multi-processor model. In this thesis we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O(1)-competitive for weighted flow time.
This thesis also initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant single-processor setting [3, 10] and has produced O(1)-competitive online algorithm for jobs with arbitrary weights and penalties. This thesis gives the first non-clairvoyant algorithms that are O(1)-competitive for minimizing the total user cost on a single processor and multi-processors, when using slightly faster (i.e., (1 + ∈)-speed for any ∈> 0) processors. Note that if no extra speed is allowed, no online algorithm can be O(1)-competitive even for minimizing (unweighted) flow time alone.
The above results assume a processor running at a fixed speed. This thesis shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the above-mentioned user cost and energy. This thesis gives two O(1)-competitive non-clairvoyant algorithms for minimizing the user cost plus energy on a single processor and multi-processors, respectively.<br>published_or_final_version<br>Computer Science<br>Master<br>Master of Philosophy
22
Hung, Yee-shing Regant, and 洪宜成. "Scheduling online batching systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2005. http://hub.hku.hk/bib/B34624016.
Full text
23
Okamoto, Kazuya. "Efficient Algorithms for Stable Matching and Online Scheduling Problems." 京都大学 (Kyoto University), 2009. http://hdl.handle.net/2433/123858.
Full text
24
Pietrzyk, Peter [Verfasser]. "Local and online algorithms for facility location / Peter Pietrzyk." Paderborn : Universitätsbibliothek, 2013. http://d-nb.info/1046073702/34.
Full text
25
Wong, Chiu Wai M. Eng Massachusetts Institute of Technology. "Competitive algorithms for online matching and vertex cover problems." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/85521.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 73-75).<br>The past decade has witnessed an explosion of research on the online bipartite matching problem. Surprisingly, its dual problem, online bipartite vertex cover, has never been explicitly studied before. One of the motivation for studying this problem is that it significantly generalizes the classical ski rental problem. An instance of such problems specifies a bipartite graph G = (L, R, E) whose left vertices L are offline and right vertices arrive online one at a time. An algorithm must maintain a valid vertex cover from which no vertex can ever be removed. The objective is to minimize the size of the cover. In this thesis, we introduce a charging-based algorithmic framework for this problem as well as its generalizations. One immediate outcome is a simple analysis of an optimal 1/1-1/e- competitive algorithm for online bipartite vertex cover. By extending the charging-based analysis in various nontrivial ways, we also obtain optimal l_1 e-competitive algorithms for the edge-weighted and submodular versions of online bipartite vertex cover, which all match the best performance of ski rental. As an application, we show that by analyzing our algorithm in the primal-dual framework, our result on submodular vertex cover implies an optimal (1/1-1/e)-competitive algorithm for its dual, online bipartite submodular matching. This problem is a generalization of online bipartite matching and may have applications in display ad allocation. We consider also the more general scenario where all the vertices are online and the graph is not necessarily bipartite, which is known as the online fractional vertex cover and matching problems. Our contribution in this direction is a primal-dual 1.901-competitive (or 1/1.901 ~~ 0.526) algorithm for these problems. Previously, it was only known that they admit a simple well-known 2-competitive (or 1/2) greedy algorithm. Our result is the first successful attempt to beat the greedy algorithm for these two problems. Moreover, our algorithm for the online matching problem significantly generalizes the traditional online bipartite graph matching problem, where vertices from only one side of the bipartite graph arrive online. In particular, our algorithm improves upon the result of the fractional version of the online edge-selection problem in Blum et. al. (JACM '06). Finally, on the hardness side, we show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs.<br>by Chiu Wai Wong.<br>M. Eng.
26
Renault, Marc Paul. "Lower and upper bounds for online algorithms with advice." Paris 7, 2014. http://www.theses.fr/2014PA077196.
Full textAbstract:
Les algorithmes en ligne fonctionnent dans un contexte où l'entrée est révélé au fur et à mesure du temps; chaque morceau révélé est appelé une demande. Après réception de chaque demahde, les algorithmes en ligne doivent prendre une action avant que la prochaine demande soit révélée, c'est-à-dire que les algorithmes en ligne doivent prendre une décision irrévocable basée sur les demandes déjà révélées sans aucune connaissance des demandes à venir. Le but est d'optimiser une fonction de coût dépendante de l'entrée. L'analyse compétitive est la méthode standard utilisée pour analyser la qualité des algorithmes en ligne. Le ratio compétitif est un ratio de pire cas, parmi toutes les séquences de demande finis, entre la performance de l'algorithme en ligne contre un algorithme optimal hors ligne pour la même séquence. Le ratio compétitif compare la performance d'un algorithme sans aucune connaissance de l'avenir contre un algorithme en pleine connaissance de l'avenir. Car l'absence totale de connaissance de l'avenir n'est souvent pas une hypothèse raisonnable, des modèles ont été proposés, appelés algorithmes en ligne avec conseil, qui donne les algorithmes en ligne l'accès à une quantité quantifiée des connaissances de l'avenir. L'intérêt de ce modèle est d'examiner comment le ratio compétitif change en fonction de la quantité de conseil. Dans cette thèse, il est présenté des bornes supérieures et inférieures dans ce modèle pour des problèmes en ligne classiques, tels que le problème de la k-serveur, de bin packing, de dual bin packing (sac à dos multiple), d'ordonnancement sur m machines identiques, du tampon de réordonnancement et de la mise à jour de la liste<br>Online algorithms operate in a setting where the input is revealed piece by piece; the pieces are called requests. After receiving each request, online algorithms must take an action before the next request is revealed, i. E. Online algorithms must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. The goal is to optimize some cost function over the input. Competitive analysis is the standard method used to analyse the quality of online algorithms. The competitive ratio is the worst case ratio, over all valid finite request sequences, of the online algorithm's performance against an optimal offline algorithm for the same request sequence. The competitive ratio compares the performance of an algorithm with no knowledge about the future against an algorithm with full knowledge about the future. Since the complete absence of future knowledge is often not a reasonable assumption, models, termed online algorithms with advice, which give the online algorithms access to a quantified amount of future knowledge, have been proposed. The interest in this model is in examining how the competitive ratio changes as a function of the amount of advice. In this thesis, we present upper and lower bounds in the advice model for classical online problems such as the k-server problem, the bin packing problem, the dual bin packing (multiple knapsack) problem, scheduling problem on m identical machines, the reordering buffer management problem and the list update problem
27
Saint-Guillain, Michael. "Models and algorithms for online stochastic vehicle routing problems." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEI068.
Full textAbstract:
Quels seront les objectifs et défis des métropoles de demain ? La plupart des problèmes issus du monde réel sont sujets à l'inconnu, nécessitant de prendre de nouvelles décisions de façon dynamique, à la demande, en fonction des évènements aléatoires qui se réalisent. Dans cette thèse, nous nous attaquons à un problème majeur, du moins en perspectives: la gestion dynamique d'une flotte de véhicules en contexte urbain. Les applications pratiques des tournées de véhicules à la demande sont nombreuses, incluant les transports publics intelligents, les services de livraison, les soins et interventions à domicile, etc. Étant donnés une flotte de véhicules et un ensemble de clients, chacun pouvant potentiellement et à tout moment émettre une requête nécessitant une intervention, l'objectif de cette thèse est de fournir une réponse à la question suivante. Étant donné l'état courant à un moment donné, comment gérer notre flotte de véhicules afin de maximiser l'espérance du nombre total de requêtes satisfaites à la fin de la journée ? Ou encore, comment minimiser l'espérance du délai moyen d'intervention de nos véhicules ? Bien entendu, la difficulté réside en ce que la plupart des requêtes, avant d'apparaître dynamiquement, ne sont pas connues. Pour chaque problème, nous considérons qu'il nous est fourni une connaissance, sous forme d'information probabiliste, telle que la probabilité qu'une requête apparaisse à un certain endroit, et à un certain moment de la journée. Grâce à des techniques issues de la recherche opérationnelle et de la programmation stochastique, nous sommes en mesure de construire et résoudre des modèles calculant les actions anticipatives les plus adéquates, comme le redéploiement préventif des véhicules, minimisant le coût total espéré, ou encore maximisant la qualité de service. La question de l'optimisation sous incertitude se pose depuis déjà plusieurs décennies. Grâce aux avancées à la fois théoriques et technologiques, nous sommes chaque jour un peu plus en mesure de palier à l'inconnu. Cependant, la plupart des problèmes intéressants restent extrêmement difficiles à résoudre, si ce n'est impossible. Il reste beaucoup à faire. Cette thèse explore certains concepts fondamentaux de l'optimisation sous incertitude. En intégrant une composante stochastique aux modèles à optimiser, nous verrons ensemble comment il est en effet possible de créer de l'anticipation<br>What will be tomorrow's big cities objectives and challenges? Most of the operational problems from the real world are inherently subject to uncertainty, requiring the decision system to compute new decisions dynamically, as random events occur. In this thesis, we aim at tackling an important growing problem in urban context: online dynamic vehicle routing. Applications of online vehicle routing in the society are manyfold, from intelligent on demand public transportation to sameday delivery services and responsive home healthcare. Given a fleet of vehicles and a set of customers, each being potentially able to request a service at any moment, the current thesis aims at answering the following question. Provided the current state at some moment of the day, which are the best vehicle actions such that the expected number of satisfied requests is maximized by the end of the operational day? How can we minimize the expected average intervention delays of our mobile units? Naturally, most of the requests remain unknown until they appear, hence being revealed online. We assume a stochastic knowledge on each operational problem we tackle, such as the probability that customer request arise at a given location and a given time of the day. By using techniques from operations research and stochastic programming, we are able to build and solve mathematical models that compute near-optimal anticipative actions, such as preventive vehicle relocations, in order to either minimize the overall expected costs or maximize the quality of service. Optimization under uncertainty is definitely not a recent issue. Thanks to evolution of both theoretical and technological tools, our ability to face the unknown constantly grows. However, most of the interesting problems remain extremely hard, if not impossible, to solve. There is still a lot of work. Generally speaking, this thesis explores some fundamentals of optimization under uncertainty. By integrating a stochastic component into the models to be optimized, we will see how it is in fact possible to create anticipation
28
Verschae, Tannenbaum Jose Claudio Verfasser], and Martin [Akademischer Betreuer] [Skutella. "The Power of Recourse in Online Optimization: Robust Solutions for Scheduling, Matroid and MST Problems / Jose Claudio Verschae Tannenbaum. Betreuer: Martin Skutella." Berlin : Universitätsbibliothek der Technischen Universität Berlin, 2012. http://d-nb.info/1020057424/34.
Full text
29
Cunningham, James. "Efficient, Parameter-Free Online Clustering." The Ohio State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1606762403895603.
Full text
30
San, Felice Mário César 1985. "Online facility location and Steiner problems = Problemas online de localização de instalações e de Steiner." [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275552.
Full textAbstract:
Orientador: Orlando Lee<br>Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação<br>Made available in DSpace on 2018-08-27T12:18:11Z (GMT). No. of bitstreams: 1
SanFelice_MarioCesar_D.pdf: 1457706 bytes, checksum: 4813f4ed44c52462656d56537d73d5dc (MD5)
Previous issue date: 2015<br>Resumo: Nesta tese estudamos problemas online das famílias de localização de instalações e de Steiner, através da abordagem de análise competitiva. O objetivo nestes problemas é construir uma rede de custo mínimo para atender a uma determinada demanda. Nós apresentamos resultados conhecidos para o problema Online da Localização de Instalações (OFL), o problema Online da Árvore de Steiner (OST) e o problema Online Single-Source Rent-or-Buy (OSRoB). O OFL consiste em atender a um conjunto de clientes, através da abertura de algumas instalações e da conexão de cada cliente com uma instalação aberta. O OST tem por objetivo conectar um conjunto de terminais utilizando uma árvore, que pode conter vértices não terminais, chamados vértices de Steiner. O OSRoB é uma versão rent-or-buy do OST, onde todos os terminais devem ser conectados a um nó especial chamado raíz. Os algoritmos e técnicas que apresentamos para estes problemas são importantes no desenvolvimento dos nossos algoritmos para os problemas que consideramos. Apresentamos novos resultados para o problema Online da Localização de Instalações com Coleta de Prêmios (OPFL), o problema Online da Árvore Estrela de Steiner (OSTS), e o problema Online da Localização de Instalações Conectadas (OCFL). O OPFL é uma generalização do OFL, em que alguns clientes podem ficar desconectados mediante o pagamento de penalidades. O OSTS é uma variante do OST, em que os vértices possuem custos não negativos. O OCFL é uma combinação do OFL e do OST, em que um conjunto de clientes precisa ser atendido através da abertura de algumas instalações, da conexão de cada cliente com uma instalação aberta, e da construção de uma árvore, mais custosa, que conecta as instalações abertas<br>Abstract: In this thesis we study online problems from the facility location and Steiner families, through the point of view of competitive analysis. The goal in these problems is to build a minimum cost network to attend a certain demand. We present known results for the Online Facility Location problem (OFL), the Online Steiner Tree problem (OST) and the Online Single-Source Rent-or-Buy problem (OSRoB). The OFL consists of serving a set of clients by opening some facilities and by connecting each client to a facility. The OST aims to connect a set of terminals in order to create a tree network, that may contain nonterminals, called Steiner nodes. The OSRoB is a rent-or-buy version of the OST, in which all terminals must be connected to a special node called root. The algorithms and techniques that we present for these problems play an important role in the design of our algorithms for the problems we consider. We present new results for the Online Prize-Collecting Facility Location problem (OPFL), the Online Steiner Tree Star problem (OSTS), and the Online Connected Facility Location problem (OCFL). The OPFL is a generalization of the OFL, in which some clients may be left unconnected by paying a penalty. The OSTS is a variant of the OST, in which the nodes have non-negative costs. The OCFL is a combination of the OFL and the OST, in which a set of clients needs to be served by opening some facilities, by connecting each client to a facility, and by creating a more expensive tree network that connects the open facilities<br>Doutorado<br>Ciência da Computação<br>Doutor em Ciência da Computação
31
Kamphans, Tom [Verfasser]. "Models and Algorithms for Online Exploration and Search / Tom Kamphans." Aachen : Shaker, 2011. http://d-nb.info/1098040260/34.
Full text
32
Han, Xin. "Online and approximation algorithms for bin-packing and knapsack problems." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135979.
Full text
33
Saintillan, Yves. "Performance evaluation of online call routing and admission control algorithms." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0005/MQ43558.pdf.
Full text
34
Angelopoulos, Spyros. "Efficient online algorithms for multicasting with bandwidth and delay guarantees." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0004/MQ45942.pdf.
Full text
35
Liu, Ming. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." Phd thesis, Ecole Centrale Paris, 2009. http://tel.archives-ouvertes.fr/tel-00453316.
Full textAbstract:
Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d'ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l'avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l'ordonnancement en ligne. Dans un problème d'ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L'analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d'une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l'aide de l'analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure.
36
Bender, Marco [Verfasser]. "Randomized Approximation and Online Algorithms for Assignment Problems / Marco Bender." München : Verlag Dr. Hut, 2015. http://d-nb.info/1074063333/34.
Full text
37
Lee, Lap-kei, and 李立基. "New results on online job scheduling and data stream algorithms." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B42182451.
Full text
38
Chan, Sze-hang, and 陳思行. "Competitive online job scheduling algorithms under different energy management models." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2013. http://hdl.handle.net/10722/206690.
Full textAbstract:
Online flow-time scheduling is a fundamental problem in computer science and has been extensively studied for years. It is about how to design a scheduler to serve computer jobs with unpredictable arrival times and varying sizes and priorities so as to minimize the total flow time (better understood as response time) of jobs. It has many applications, most notable in the operating of server farms. As energy has become an important issue, the design of scheduler also has to take power management into consideration, for example, how to scale the speed of the processors dynamically. The objectives are orthogonal as one would prefer lower processor speed to save energy, yet a good quality of service must be retained. In this thesis, I study a few scheduling problems for energy and flow time in depth and give new algorithms to tackle them. The competitiveness of our algorithms is guaranteed with worst-case mathematical analysis against the best possible or hypothetical solutions.
In the speed scaling model, the power of a processor increases with its speed according to a certain function (e.g., a cubic function of speed). Among all online scheduling problems with speed scaling, the nonclairvoyant setting (in which the size of a job is not known during its execution) with arbitrary priorities is perhaps the most challenging. This thesis gives the first competitive algorithm called WLAPS for this setting.
In reality, it is not uncommon that during the peak-load period, some (low-priority) users have their jobs rejected by the servers. This triggers me to study more complicated scheduling algorithms that can strike a good balance among speed scaling, flow time and rejection penalty. Two new algorithms UPUW and HDFAC for different models of rejection penalty have been proposed and analyzed.
Last, but perhaps the most interesting, we study power management in large server farm environment in which the primary energy saving mechanism is to put some processors to sleep. Two new algorithms POOL and SATA have been designed to tackle jobs that cannot and can migrate among the processors, respectively. They are integrated algorithms that can consider speed scaling, job scheduling and processor sleep management together to optimize the energy usage and ow time simultaneously. These algorithms are again proven mathematically to be competitive even in the worst case.<br>published_or_final_version<br>Computer Science<br>Doctoral<br>Doctor of Philosophy
39
Lee, Lap-kei. "New results on online job scheduling and data stream algorithms." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B42182451.
Full text
40
Liu, Ming Chu Chengbin. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." S. l. : S. n, 2009. http://theses.abes.fr/2009ECAP0028.
Full text
41
Havill, Jessen Tait. "Analysis of algorithms for online routing and scheduling in networks." W&M ScholarWorks, 1998. https://scholarworks.wm.edu/etd/1539623929.
Full textAbstract:
We study situations in which an algorithm must make decisions about how to best route and schedule data transfer requests in a communication network before each transfer leaves its source. For some situations, such as those requiring quality of service guarantees, this is essential. For other situations, doing work in advance can simplify decisions in transit and increase the speed of the network. In order to reflect realistic scenarios, we require that our algorithms be online, or make their decisions without knowing future requests. We measure the efficiency of an online algorithm by its competitive ratio, which is the maximum ratio, over all request sequences, of the cost of the online algorithm's solution to that of an optimal solution constructed by knowing all the requests in advance.;We identify and study two distinct variations of this general problem. In the first, data transfer requests are permanent virtual circuit requests in a circuit-switched network and the goal is to minimize the network congestion caused by the route assignment. In the second variation, data transfer requests are packets in a packet-switched network and the goal is to minimize the makespan of the schedule, or the time that the last packet reaches its destination. We present new lower bounds on the competitive ratio of any online algorithm with respect to both network congestion and makespan.;We consider two greedy online algorithms for permanent virtual circuit routing on arbitrary networks with unit capacity links, and prove both lower and upper bounds on their competitive ratios. While these greedy algorithms are not optimal, they can be expected to perform well in many circumstances and require less time to make a decision, when compared to a previously discovered asymptotically optimal online algorithm. For the online packet routing and scheduling problem, we consider an algorithm which simply assigns to each packet a priority based upon its arrival time. No packet is delayed by another packet with a lower priority. We analyze the competitive ratio of this algorithm on linear array, tree, and ring networks.
42
Zhang, Lele. "On-line scheduling with constraints /." Connect to thesis, 2009. http://repository.unimelb.edu.au/10187/3538.
Full text
43
Fung, Ping-yuen. "Online algorithms for the provision of quality of service in networks." Click to view the E-thesis via HKUTO, 2005. http://sunzi.lib.hku.hk/hkuto/record/B3158052X.
Full text
44
Minerva, Michela. "Automated Configuration of Offline/Online Algorithms: an Empirical Model Learning Approach." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/22649/.
Full textAbstract:
The energy management system is the intelligent core of a virtual power plant and it manages power flows among units in the grid. This implies dealing with optimization under uncertainty because entities such as loads and renewable energy resources have stochastic behaviors. A hybrid offline/online optimization technique can be applied in such problems to ensure efficient online computation.
This work devises an approach that integrates machine learning and optimization models to perform automatic algorithm configuration. It is inserted as the top component in a two-level hierarchical optimization system for the VPP, with the goal of configuring the low-level offline/online optimizer.
Data from the low-level algorithm is used for training machine learning models - decision trees and neural networks – that capture the highly complex behavior of both the controlled VPP and the offline/online optimizer. Then, Empirical Model Learning is adopted to build the optimization problem, integrating usual mathematical programming and ML models.
The proposed approach successfully combines optimization and machine learning in a data-driven and flexible tool that performs automatic configuration and forecasting of the low-level algorithm for unseen input instances.
45
Ochel, Marcel [Verfasser]. "Approximation and online algorithms for selected network optimization problems / Marcel Ochel." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2013. http://d-nb.info/1035688484/34.
Full text
46
Fung, Ping-yuen, and 馮秉遠. "Online algorithms for the provision of quality of service in networks." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2005. http://hub.hku.hk/bib/B3158052X.
Full text
47
HANDA, MANISH. "ONLINE PLACEMENT AND SCHEDULING ALGORITHMS AND METHODOLOGIES FOR RECONFIGURABLE COMPUTING SYSTEMS." University of Cincinnati / OhioLINK, 2004. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1100030953.
Full text
48
Harrington, Edward, and edwardharrington@homemail com au. "Aspects of Online Learning." The Australian National University. Research School of Information Sciences and Engineering, 2004. http://thesis.anu.edu.au./public/adt-ANU20060328.160810.
Full textAbstract:
Online learning algorithms have several key advantages compared to their batch learning algorithm counterparts: they are generally more memory efficient, and computationally mor efficient; they are simpler to implement; and they are able to adapt to changes where the learning model is time varying. Online algorithms because of their simplicity are very appealing to practitioners. his thesis investigates several online learning algorithms and their application. The thesis has an underlying theme of the idea of combining several simple algorithms to give better performance. In this thesis we investigate: combining weights, combining hypothesis, and (sort of) hierarchical combining.¶
Firstly, we propose a new online variant of the Bayes point machine (BPM), called the online Bayes point machine (OBPM). We study the theoretical and empirical performance of the OBPm algorithm. We show that the empirical performance of the OBPM algorithm is comparable with other large margin classifier methods such as the approximately large margin algorithm (ALMA) and methods which maximise the margin explicitly, like the support vector machine (SVM). The OBPM algorithm when used with a parallel architecture offers potential computational savings compared to ALMA. We compare the test error performance of the OBPM algorithm with other online algorithms: the Perceptron, the voted-Perceptron, and Bagging. We demonstrate that the combinationof the voted-Perceptron algorithm and the OBPM algorithm, called voted-OBPM algorithm has better test error performance than the voted-Perceptron and Bagging algorithms. We investigate the use of various online voting methods against the problem of ranking, and the problem of collaborative filtering of instances. We look at the application of online Bagging and OBPM algorithms to the telecommunications problem of channel equalization. We show that both online methods were successful at reducing the effect on the test error of label flipping and additive noise.¶
Secondly, we introduce a new mixture of experts algorithm, the fixed-share hierarchy (FSH) algorithm. The FSH algorithm is able to track the mixture of experts when the switching rate between the best experts may not be constant. We study the theoretical aspects of the FSH and the practical application of it to adaptive equalization. Using simulations we show that the FSH algorithm is able to track the best expert, or mixture of experts, in both the case where the switching rate is constant and the case where the switching rate is time varying.
49
Tripathi, Pushkar. "Allocation problems with partial information." Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44789.
Full textAbstract:
Allocation problems have been central to the development of the theory of algorithms and also find applications in several realms of computer science and economics. In this thesis we initiate a systematic study of these problems in situations with limited information.
Towards this end we explore several modes by which data may be obfuscated from the algorithm. We begin by investigating temporal constraints where data is revealed to the algorithm over time. Concretely, we consider the online bipartite matching problem in the unknown distribution model and present the first algorithm that breaches the 1-1/e barrier for this problem.
Next we study issues arising from data acquisition costs that are prevalent in ad-systems and kidney exchanges. Motivated by these constraints we introduce the query-commit model and present constant factor algorithms for the maximum matching and the adwords problem in this model.
Finally we assess the approximability of several classical allocation problems with multiple agents having complex non-linear cost functions. This presents an additional obstacle since the support for the cost functions may be extremely large entailing oracle access. We show tight information theoretic lower bounds for the general class of submodular functions and also extend these results to get lower bounds for a subclass of succinctly representable non-linear cost functions.
50
Lorenz, Julian Michael. "Optimal trading algorithms : portfolio transactions, multiperiod portfolio selection, and competitive online search /." Zürich : ETH, 2008. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=17746.
Full text