<p dir="ltr">We analyze the query complexity of multiple search problems.</p><p dir="ltr">Firstly, we provide lower bounds on the complexity of "Local Search". In local search we are given a graph G and oracle access to a function f mapping the vertices to numbers, and seek a local minimum of f; i.e. a vertex v such that f(v) <= f(u) for all neighbors u of v. We provide separate lower bounds in terms of several graph parameters, including congestion, expansion, separation number, mixing time of a random walk, and spectral gap. To aid in showing these bounds, we design and use an improved relational adversary method for classical algorithms, building on the prior work of Scott Aaronson. We also obtain some quantum bounds using the traditional strong weighted adversary method.</p><p dir="ltr">Secondly, we show a multiplicative duality gap for Yao's minimax lemma by studying unordered search. We then go on to give tighter than asymptotic bounds for unordered and ordered search in rounds. Inspired by a connection through sorting with rank queries, we also provide tight asymptotic bounds for proportional cake cutting in rounds.</p>

Tourists' information processing is a dynamic process in that their information use depends on the surrounding context. From tourists' personal characteristics (e.g., age, gender, and travel experience), nature of tourism products (e.g., intangibility and variability), to the development of information technology (e.g., the prevalent usage of mobile devices for information search), a variety of contextual factors are involved when tourists process information for decision-making. Given the importance of online reviews in the hospitality and tourism field as information sources, this dissertation aims to understand the contextual effects of online reviews on tourists' decision-making. By selecting several contextual factors, three independent and interrelated essays examine how tourists' cognitive or behavioral responses to online reviews are affected by those factors. Considering that local search (e.g., looking for nearby restaurants by using "restaurants near me" as a search query) becomes an important context for using online reviews, both Study 1 and 2 focus on the local search context. Study 1 investigates the role of online reviews in the local search context; specifically, how online reviews are used as ranking factors by local search platforms (LSPs), is examined with an analytical approach. Study 2 investigates tourists' processing of online reviews in the local search context; specifically, how online reviews are differently processed in the local search context (e.g., searching for a restaurant that can be visited immediately) compared with the non-local context (e.g., searching for a restaurant that can be visited in a month), is examined by conducting an experiment. Building on Study 2, Study 3 investigates how tourists' processing of online reviews is affected by another contextual factor, the nature of tourism products; specifically, how the variability of tourism products (i.e., their change in quality over time) influences the way tourists process online reviews, is examined through social media analytics. Results of the three essays provide empirical support for the underlying argument of this dissertation: understanding tourists' responses to online reviews depends on factors that transcend their information characteristics. As a whole, the findings of this dissertation suggest the need for considering the surrounding context to further understand how online reviews affect tourists' decision-making. As practical implications, this dissertation discusses the importance of leveraging various types of information about tourists' context (e.g., location accessed from smartphones, and physiological condition accessed through smartwatches). / Doctor of Philosophy / Tourists use online reviews within specific situations. The effects of such reviews on tourists' decision-making are difficult to explain without considering the surrounding contexts. Depending on when (e.g., before or during the trip), where (e.g., at home or destination), or for which products (e.g., restaurants, attractions, or hotels) they use online reviews, even the same online review can be differently perceived by tourists (e.g., how helpful it is). Therefore, the reviews have an increased or reduced influence on their product choices. This dissertation aims to understand the context-dependence of tourist's use of online reviews. The three essays in this dissertation examine how online reviews are used or processed by tourists under certain context: how online reviews affect tourist's decision-making in the local search context (e.g., searching for "restaurants near me" using smartphones during the trip) (Study 1); how tourists process online reviews while relying on reviews for immediately choosing places to visit (Study 2); and how tourists perceive online reviews when they are recently posted (Study 3). The findings confirm the dynamic nature of tourist's use of online reviews and offer several insights for tourism businesses to hone their strategies on marketing online reviews.

Generalized hill climbing (GHC) algorithms provide a framework for using local search algorithms to address intractable discrete optimization problems. Many well-known local search algorithms can be formulated as GHC algorithms, including simulated annealing, threshold accepting, Monte Carlo search, and pure local search (among others). This dissertation develops a mathematical framework for simultaneously addressing a set of related discrete optimization problems using GHC algorithms. The resulting algorithms, termed simultaneous generalized hill climbing (SGHC) algorithms, can be applied to a wide variety of sets of related discrete optimization problems. The SGHC algorithm probabilistically moves between these discrete optimization problems according to a problem generation probability function. This dissertation establishes that the problem generation probability function is a stochastic process that satisfies the Markov property. Therefore, given a SGHC algorithm, movement between these discrete optimization problems can be modeled as a Markov chain. Sufficient conditions that guarantee that this Markov chain has a uniform stationary probability distribution are presented. Moreover, sufficient conditions are obtained that guarantee that a SGHC algorithm will visit the globally optimal solution over all the problems in a set of related discrete optimization problems. Computational results are presented with SGHC algorithms for a set of traveling salesman problems. For comparison purposes, GHC algorithms are also applied individually to each traveling salesman problem. These computational results suggest that optimal/near optimal solutions can often be reached more quickly using a SGHC algorithm. / Ph. D.

Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested. / Ph. D.

Mini Rotorcraft Unmanned Aerial Vehicles (MRUAVs) flown at low altitude as a part of a human-robot team are potential sources of tactical information for local search missions. Traditionally, their effectiveness in this role has been limited by an inability to intelligently perceive unknown environments or integrate with human team members. Human-robot collaboration provides the theory for building cooperative relationships in this context. This theory, however, only addresses those human-robot teams that are either robot-centered or human-centered in their decision making processes or relationships. This work establishes a new branch of human-robot collaborative theory, Operator Blending, which creates codependent and cooperative relationships between a single robot and human team member for tactical missions. Joint Intension Theory is the basis of this approach, which allows both the human and robot to contribute what each does well in accomplishing the mission objectives. Information processing methods for shared visual information and object tracking take advantage of the human role in the perception process. In addition, coupling of translational commands and the search process establish navigation as the shared basis of communication between the MRUAV and human, for system integration purposes. Observation models relevant to both human and robotic collaborators are tracked through a boundary based approach deemed AIM-SHIFT. A system is developed to classify the semantic and functional relevance of an observation model to local search called the Code of Observational Genetics (COG). These COGs are used to qualitatively map the environment through Qualitative Unsupervised Intelligent Collaborative Keypoint (QUICK) mapping, created to support these methods. / Ph. D.

Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions. / Ph. D.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-15T14:59:59Z No. of bitstreams: 1 marcoshenriquefonsecaribeiro.pdf: 12873424 bytes, checksum: 2b2b91fd2a9726856a0486afa760fe2c (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-17T16:01:12Z (GMT) No. of bitstreams: 1 marcoshenriquefonsecaribeiro.pdf: 12873424 bytes, checksum: 2b2b91fd2a9726856a0486afa760fe2c (MD5) / Made available in DSpace on 2017-05-17T16:01:12Z (GMT). No. of bitstreams: 1 marcoshenriquefonsecaribeiro.pdf: 12873424 bytes, checksum: 2b2b91fd2a9726856a0486afa760fe2c (MD5) Previous issue date: 2016-10-03 / A Tomografia por Impedância Elétrica (TIE) consiste em uma técnica onde imagens são construídas a partir da injeção de uma corrente elétrica em determinado meios, seguida da leitura de valores de potencial elétrico em pontos do contorno externo de tal domínio. Desta maneira, conhecendo-se ou estimando-se a condutividade elétrica de regiões internas ao meio, pode-se inferir aspectos geométricos da composição do mesmo. Trabalhos na literatura aplicam esta técnica ao contexto de obtenção de imagens do tórax humano, com objetivo de estimar a geometria das cavidades cardíacas de um determinado paciente. O objetivo final de estudo deste trabalho, dentro do contexto de aplicação da TIE à obtenção de cavidades cardíacas, é propor uma metodologia para a estimação da Fração de Ejeção Cardíaca, ou simplesmente Fração de Ejeção (FE), que consiste em medir o percentual de volume de sangue expulso dos ventrículos ao final de um ciclo de batimento do coração. Este trabalho visa evoluir outros trabalhos já existentes que modelam o problema acima descrito como sendo um problema inverso, de otimização, onde se pretende minimizar a diferença entre valores de potencial elétrico medidos e valores simulados por modelos computacionais. A evolução se dá em níveis diferentes. No primeiro nível, é feito um avanço sobre as técnicas de otimização para a resolução do problema inverso, em sua formulaçãobidimensional. Paratal, épropostaumametaheurísticaqueauxiliamétodosde buscanaobtençãodevaloresmaisacurados. Estametaheurísticaéapresentadaemversões sequencial e paralela. São apresentados resultados computacionais de testes realizados para este primeiro nível. Em um segundo nível, é feita a modelagem em três dimensões das mesmas abordagens já encontradas na literatura, que, para a aplicação específica da determinação da FE, até então estão limitadas a modelos bidimensionais. Assim, todo o problema é revisto para uma nova proposta de modelagem, que inclui a criação de modelos geométricos tridimensionais para as regiões de interesse do problema. Como principal contribuição do trabalho neste segundo nível, encontra-se um esquema de parametrização das malhas de polígonos que modelam ventrículos do coração, de forma que se tenha uma maneira compacta de representar as mesmas e, ao mesmo tempo, diminuindo o custo computacional do método de otimização por meio de drástica redução do número de variáveis do problema. Por fim, também é realizado um estudo preliminar da sensibilidade da técnica à presença de ruídos nos dados de entrada. / The Electrical Impedance Tomography (EIT) consists in a technique where images are constructed from the measurements of the electrical potential in some points on the external boundary of some specific domain, caused by the injection of an electrical current in such domain. This way, knowing or estimating the electrical conductivity of some regions inside the domain, geometric aspects of the composition of that domain can be inferred. Works in literature apply this technique to the context of obtaining images from the human thorax, with the objective of estimating the geometry of some cardiac cavities of a specific patient. The final goal of this work, inside the context of the obtention of cardiac cavities, is to propose a methodology for estimating the Cardiac Ejection Fraction, orsimplyEjectionFraction(EF),whichconsistsinmeasuringthepercentualofthevolume of blood expelled from the ventricles at the end of a heart beat cicle. This work intends to evolute previous works, that models the above mentioned problem as an inverse problem, an optimization problem, where the intention is to minimize the difference between the values of measured electrical potentials and the values obtained through simulation using computational models. This evolution occurs in different levels. In the first level, is performedanimprovementoverthepre-existentoptimizationtechniquesforthesolutionof theinverseproblem,inatwodimensionalversion. Forthis,isproposedametaheuristicthat assistssearchmethodstowardstheobtentionofmoreaccuratedvalues. Suchmetaheuristic is presented in sequential and parallel versions. Computational results for performed tests for this level are presented. In a second level, a three dimensional modeling of the same approaches found in literature is done. Those approaches, for the specific application of determining the EF, are so far limited to two dimensional models. Therefore, the whole problem is reviewed in order to propose a new model, which includes the creation of three dimensional geometric models for the regions of interest of the problem. As the main contribution of this work in that second level, there is a parameterization schema of the polygon meshes that model heart ventricles, so that it provides a compact way of representing such meshes, and, at the same time, a way of reducing the computational cost of the optimization method by means of a drastic reduction of the number of variables of the problem. Finally, a preliminary study of the sensibility of the technique to the presence of noise in the input data is also performed.

Das Konzept von aktiven Brownschen Teilchen kann benutzt werden, um das Verhalten einfacher biologischer Organismen oder künstlicher Objekte, welche die Möglichkeit besitzen sich von selbst fortzubewegen zu beschreiben. Als Bewegungsgleichungen für aktive Brownsche Teilchen kommen Langevin Gleichungen zum Einsatz. In dieser Arbeit werden aktive Teilchen mit konstanter Geschwindigkeit diskutiert. Im ersten Teil der Arbeit wirkt auf die Bewegungsrichtung des Teilchen weißes alpha-stabiles Rauschen. Es werden die mittlere quadratische Verschiebung und der effektive Diffusionskoeffizient bestimmt. Eine überdampfte Beschreibung, gültig für Zeiten groß gegenüber der Relaxationszeit wird hergleitet. Als experimentell zugängliche Meßgröße, welche als Unterscheidungsmerkmal für die unterschiedlichen Rauscharten herangezogen werden kann, wird die Kurtose berechnet. Neben weißem Rauschen wird noch der Fall eines Ornstein-Uhlenbeck Prozesses angetrieben von Cauchy verteiltem Rauschen diskutiert. Während eine normale Diffusion mit zu weißem Rauschen identischem Diffusionskoeffizienten bestimmt wird, kann die beobachtete Verteilung der Verschiebungen Nicht-Gaußförmig sein. Die Zeit für den Übergang zur Gaußverteilung kann deutlich größer als die Zeitskale Relaxationszeit und die Zeitskale des Ornstein-Uhlenbeck Prozesses sein. Eine Grenze der benötigten Zeit wird durch eine Näherung der Kurtosis ermittelt. Weiterhin werden die Grundlagen eines stochastischen Modells für lokale Suche gelegt. Lokale Suche ist die Suche in der näheren Umgebung eines bestimmten Punktes, welcher Haus genannt wird. Abermals diskutieren wir ein aktives Teilchen mit unveränderlichem Absolutbetrag der Geschwindigkeit und weißen alpha-stabilem Rauschen in der Bewegungsrichtungsdynamik. Die deterministische Bewegung des Teilchens wird analysiert bevor die Situation mit Rauschen betrachtet wird. Die stationäre Aufenthaltswahrscheinlichkeitsdichtefunktion wird bestimmt. Es wird eine optimale Rauschstärke für die lokale Suche, das heißt für das Auffinden eines neuen Ortes in kleinstmöglicher Zeit festgestellt. Die kleinstmögliche Zeit wird kaum von der Rauschart abhängen. Wir werden jedoch feststellen, dass die Rauschart deutlichen Einfluß auf die Rückkehrwahrscheinlichkeit zum Haus hat, wenn die Richtung des zu Hauses fehlerbehaftet ist. Weiterhin wird das Model durch eine an das Haus abstandsabhängige Kopplung erweitert werden. Zum Abschluß betrachten wir eine Gruppe von Suchern. / Active Brownian particles described by Langevin equations are used to model the behavior of simple biological organisms or artificial objects that are able to perform self propulsion. In this thesis we discuss active particles with constant speed. In the first part, we consider angular driving by white Levy-stable noise and we discuss the mean squared displacement and diffusion coefficients. We derive an overdamped description for those particles that is valid at time scales larger the relaxation time. In order to provide an experimentally accessible property that distinguishes between the considered noise types, we derive an analytical expression for the kurtosis. Afterwards, we consider an Ornstein-Uhlenbeck process driven by Cauchy noise in the angular dynamics of the particle. While, we find normal diffusion with the diffusion coefficient identical to the white noise case we observe a Non-Gaussian displacement at time scales that can be considerable larger than the relaxation time and the time scale provided by the Ornstein-Uhlenbeck process. In order to provide a limit for the time needed for the transition to a Gaussian displacement, we approximate the kurtosis. Afterwards, we lay the foundation for a stochastic model for local search. Local search is concerned with the neighborhood of a given spot called home. We consider an active particle with constant speed and alpha-stable noise in the dynamics of the direction of motion. The deterministic motion will be discussed before considering the noise to be present. An analytical result for the steady state spatial density will be given. We will find an optimal noise strength for the local search and only a weak dependence on the considered noise types. Several extensions to the introduced model will then be considered. One extension includes a distance dependent coupling towards the home and thus the model becomes more general. Another extension concerned with an erroneous understanding by the particle of the direction of the home leads to the result that the return probability to the home depends on the noise type. Finally we consider a group of searchers.

[pt] Nos últimos anos o comércio eletrônico tem se difundido na sociedade e a logística de entrega dos produtos é um dos pilares para que este mercado mantenha o nível de serviço alto e continue sendo vantajoso para o consumidor decidir por realizar a compra pela internet. O presente trabalho se destina a estudar sobre o problema de roteamento de veículos de entrega last-mile para e-commerce e aplicar a metaheurística Iterated Local Search (ILS) visando otimizar o roteamento do trecho last-mile de encomendas realizadas em uma empresa de comércio eletrônico brasileira. Com o objetivo de encontrar rotas de menor custo para as entregas a serem realizadas, este trabalho propõe uma extensão para o Vehcile Routing Problem With Occasional Drivers (VRPOD),considerando frota heterogênea e motoristas ocasionais realizando o transporte de mais de uma entrega. Para a aplicação do método foram utilizados dados fornecidos por uma empresa de e-commerce que foram devidamente anonimizados de forma a não ser possível identificar a empresa e nem os clientes, respeitando os princípios éticos. Foram utilizadas 121 instâncias, sendo a menor com um vértice e a maior com 344. Os resultados do modelo proposto são apresentados em dois cenários, primeiramente considerando que o roteamento é realizado sem a utilização de motoristas ocasionais. O segundo cenário considera a disponibilização de motoristas ocasionais para serem utilizados em algumas rotas. Ambos os cenários foram comparados com as rotas geradas pelo roteador existente hoje na companhia e os resultados preliminares indicam que o sem a utilização de motoristas ocasionais o ILS proposto obtém melhores soluções em 53.72 por cento das instâncias e quando os motoristas ocasionais são incorporados a rota ocorre melhoria em 76.03 por cento das instâncias utilizadas. A utilização de motoristas ocasionais também proporciona uma redução de 10.30 por cento no custo médio de roteamento. / [en] In recent years, e-commerce has become widespread in society, and the logistics of product delivery is a crucial pillar for this market to maintain a high level of service and remain advantageous for consumers choosing to make purchases online. The present work aims to study the problem of last-mile vehicle routing for e-commerce deliveries and apply an Iterated Local Search (ILS) metaheuristic to optimize the routing of parcels in a Brazilian e-commerce company. With the objective of finding routes with the lowest cost for the deliveries, this study proposes an extension to the Vehicle Routing Problem with Occasional Drivers (VRPOD), considering a heterogeneous fleet and occasional drivers handling multiple deliveries. For the methodology application, data provided by an e-commerce company are used, and they are properly anonymized to prevent the identification of the company and its clients, respecting ethical principles. A total of 121 instances are used, ranging from the smallest with one vertex to the largest with 344. The results of the proposed model are presented in two scenarios: firstly, considering routing without the use of occasional drivers, and secondly, considering the availability of occasional drivers for some routes. Both scenarios are compared with the routes generated by the current router used in the company, and preliminary results indicate that without the use of occasional drivers, the proposed ILS obtains better solutions in 53.72 percent of the instances, and when occasional drivers are incorporated into the route, improvements occur in 76.03 percent of the instances. The utilization of occasional drivers also provides a 10.30 percent reduction in the average routing cost.

Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo. / This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.