Página 1 dos resultados de 325 itens digitais encontrados em 0.117 segundos

On the k-restricted structure ratio in planar and outerplanar graphs

CALINESCU, Gruia; FERNANDES, Cristina G.
Fonte: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE Publicador: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
65.47%
A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.; National Science Foundation NSF[CCF-0515088]

Novos paradigmas para equalização e identificação de canais baseados em estruturas não-lineares e algoritmos evolutivos; News paradigms for channel equalization and identification based on nonlinear structures and evolutionary algorithms

Romis Ribeiro de Faissol Attux
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 26/04/2005 Português
Relevância na Pesquisa
65.43%
O objetivo deste trabalho é investigar a aplicação de estruturas não-lineares e de técnicas de otimização baseadas em computação evolutiva a problemas de equalização e identificação de canal. O relato se divide em duas partes: a primeira voltada à análise dos fundamentos do problema de filtragem, e a segunda, à apresentação de novas abordagens para sua solução. A primeira parte, inaugurada pelas noções primordiais de comunicação, abrange os diferentes aspectos do projeto de um filtro. Permeia toda a exposição uma idéia fundamental: o estabelecimento de um paradigma genérico de filtragem adaptativa. Na segunda parte, apresentamos contribuições originais que se encaixam de diversas formas no espírito desse paradigma. Os problemas abordados são: equalização linear cega, equalização e pré-distorção baseadas em redes neurais, identificação cega, identificação de plantas recursivas, busca cega do receptor de máxima verossimilhança e equalização não-linear cega baseada em predição. Tais propostas, além de possuírem um valor intrínseco, podem ser entendidas como um corpus de evidências da validade das idéias unificadoras pertencentes ao arcabouço teórico erigido; The objective of this work is to investigate the use of nonlinear structures and optimization techniques based on evolutionary computation in channel equalization and identification problems. The text is structured according to a twofold division: the first part is dedicated to the analysis of the foundations of the filtering problem...

Light field appearance manifolds

Christoudias, Chris Mario, 1980-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 141 p.; 6023817 bytes; 6042420 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
65.44%
Statistical shape and texture appearance models are powerful image representations, but previously had been restricted to 2D or 3D shapes with smooth surfaces and lambertian reflectance. In this thesis we present a novel 4D appearance model using image-based rendering techniques, which can represent complex lighting conditions, structures, and surfaces. We construct a light field manifold capturing the multi-view appearance of an object class and extend previous direct search algorithms to match new light fields or 2D images of an object to a point on this manifold. When matching to a 2D image the reconstructed light field can be used to render unseen views of the object. Our technique differs from previous view-based active appearance models in that model coefficients between views are explicitly linked, and that we do not model any pose variation within the deformable model at a single view. It overcomes the limitations of polygonal based appearance models and uses light fields that are acquired in real-time.; by Chris Mario Christoudias.; Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.; Includes bibliographical references (leaves 137-141).

Compact representations for fast nonrigid registration of medical images

Timoner, Samson J. (Samson Joshua), 1975-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 179 p.; 16563811 bytes; 16563717 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
65.54%
We develop efficient techniques for the non-rigid registration of medical images by using representations that adapt to the anatomy found in such images. Images of anatomical structures typically have uniform intensity interiors and smooth boundaries. We create methods to represent such regions compactly using tetrahedra. Unlike voxel-based representations, tetrahedra can accurately describe the expected smooth surfaces of medical objects. Furthermore, the interior of such objects can be represented using a small number of tetrahedra. Rather than describing a medical object using tens of thousands of voxels, our representations generally contain only a few thousand elements. Tetrahedra facilitate the creation of efficient non-rigid registration algorithms based on finite element methods (FEM). We create a fast, FEM-based method to non-rigidly register segmented anatomical structures from two subjects. Using our compact tetrahedral representations, this method generally requires less than one minute of processing time on a desktop PC. We also create a novel method for the non-rigid registration of gray scale images. To facilitate a fast method, we create a tetrahedral representation of a displacement field that automatically adapts to both the anatomy in an image and to the displacement field. The resulting algorithm has a computational cost that is dominated by the number of nodes in the mesh (about 10...

Declarative symbolic pure-logic model checking

Shlyakhter, Ilya, 1975-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 181 p.; 9773619 bytes; 9796412 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
65.51%
Model checking, a technique for findings errors in systems, involves building a formal model that describes possible system behaviors and correctness conditions, and using a tool to search for model behaviors violating correctness properties. Existing model checkers are well-suited for analyzing control-intensive algorithms (e.g. network protocols with simple node state). Many important analyses, however, fall outside the capabilities of existing model checkers. Examples include checking algorithms with complex state, distributed algorithms over all network topologies, and highly declarative models. This thesis addresses the problem of building an efficient model checker that overcomes these limitations. The work builds on Alloy, a relational modeling language. Previous work has defined the language and shown that it can be analyzed by translation to SAT. The primary contributions of this thesis include: a modeling paradigm for describing complex structures in Alloy; significant improvements in scalability of the analyzer; and improvements in usability of the analyzer via addition of a debugger for over constraints. Together, these changes make model-checking practical for important new classes of analyses. While the work was done in the context of Alloy...

Segmentation of medical images under topological constraints

Ségonne, Florent, 1976-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 142 p.
Português
Relevância na Pesquisa
75.44%
Major advances in the field of medical imaging over the past two decades have provided physicians with powerful, non-invasive techniques to probe the structure, function, and pathology of the human body. This increasingly vast and detailed amount of information constitutes a great challenge for the medical imaging community, and requires significant innovations in all aspect of image processing. To achieve accurate and topologically-correct delineations of anatomical structures from medical images is a critical step for many clinical and research applications. In this thesis, we extend the theoretical tools applicable to the segmentation of images under topological control, apply these new concepts to broaden the class of segmentation methodologies, and develop generally applicable and well-founded algorithms to achieve accurate segmentations of medical images under topological constraints. First, we introduce a digital concept that offers more flexibility in controlling the topology of digital segmentations. Second, we design a level set framework that offers a subtle control over the topology of the level set components. Our method constitutes a trade-off between traditional level sets and topology-preserving level sets.; (cont.) Third...

Understanding program structure and behavior

Dharmawan, Sie Hendrata
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 122 p.
Português
Relevância na Pesquisa
75.44%
A large software system usually has structure in it. Several functions work together to accomplish a certain task, and several tasks are grouped together to perform a bigger task. In order to understand this division, one has to consult the documentations or read through the source code. However, the documentations are usually incomplete and outdated, while code inspection is tedious and impractical. Algorithms have been proposed that automatically group functions with similar functionality. In this thesis I will present LogiView, an algorithm that presents an organizational view of the functions. This view will ease the process of understanding the structures in the program, identifying functions with related tasks, and separating the functions into logical groups. I will also present a methodology of analyzing the function names in the program. This method leverages the result of the LogiView algorithm and identifies the names that are most relevant to the functionality of the program. Given a set of programs that are known to have same functionality, this method extracts the similarity in the function names and builds a dictionary of the names that are semantically related to the functionality.; (cont.) The methodology also detects when two programs have similar functionality and how to measure the similarity between multiple programs. Lastly...

Multiscale Gaussian graphical models and algorithms for large-scale inference

Choi, Myung Jin, S.M. Massachusetts Institute of Technology
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 123 p.
Português
Relevância na Pesquisa
85.54%
Graphical models provide a powerful framework for stochastic processes by representing dependencies among random variables compactly with graphs. In particular, multiscale tree-structured graphs have attracted much attention for their computational efficiency as well as their ability to capture long-range correlations. However, tree models have limited modeling power that may lead to blocky artifacts. Previous works on extending trees to pyramidal structures resorted to computationally expensive methods to get solutions due to the resulting model complexity. In this thesis, we propose a pyramidal graphical model with rich modeling power for Gaussian processes, and develop efficient inference algorithms to solve large-scale estimation problems. The pyramidal graph has statistical links between pairs of neighboring nodes within each scale as well as between adjacent scales. Although the graph has many cycles, its hierarchical structure enables us to develop a class of fast algorithms in the spirit of multipole methods. The algorithms operate by guiding far-apart nodes to communicate through coarser scales and considering only local interactions at finer scales. The consistent stochastic structure of the pyramidal graph provides great flexibilities in designing and analyzing inference algorithms. Based on emerging techniques for inference on Gaussian graphical models...

Prior information for brain parcellation

Pohl, Kilian Maria
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 184 p.
Português
Relevância na Pesquisa
65.51%
To better understand brain disease, many neuroscientists study anatomical differences between normal and diseased subjects. Frequently, they analyze medical images to locate brain structures influenced by disease. Many of these structures have weakly visible boundaries so that standard image analysis algorithms perform poorly. Instead, neuroscientists rely on manual procedures, which are time consuming and increase risks related to inter- and intra-observer reliability [53]. In order to automate this task, we develop an algorithm that robustly segments brain structures. We model the segmentation problem in a Bayesian framework, which is applicable to a variety of problems. This framework employs anatomical prior information in order to simplify the detection process. In this thesis, we experiment with different types of prior information such as spatial priors, shape models, and trees describing hierarchical anatomical relationships. We pose a maximum a posteriori probability estimation problem to find the optimal solution within our framework. From the estimation problem we derive an instance of the Expectation Maximization algorithm, which uses an initial imperfect estimate to converge to a good approximation.; (cont.) The resulting implementation is tested on a variety of studies...

Decoding algorithms for complex natural language tasks

Deshpande, Pawan
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 85 p.
Português
Relevância na Pesquisa
75.48%
This thesis focuses on developing decoding techniques for complex Natural Language Processing (NLP) tasks. The goal of decoding is to find an optimal or near optimal solution given a model that defines the goodness of a candidate. The task is challenging because in a typical problem the search space is large, and the dependencies between elements of the solution are complex. The goal of this work is two-fold. First, we are interested in developing decoding techniques with strong theoretical guarantees. We develop a decoding model based on the Integer Linear Programming paradigm which is guaranteed to compute the optimal solution and is capable of accounting for a wide range of global constraints. As an alternative, we also present a novel randomized algorithm which can guarantee an arbitrarily high probability of finding the optimal solution. We apply these methods to the task of constructing temporal graphs and to the task of title generation. Second, we are interested in carefully investigating the relations between learning and decoding. We build on the Perceptron framework to integrate the learning and decoding procedures into a single unified process. We use the resulting model to automatically generate tables-of-contents, structures with deep hierarchies and rich contextual dependencies. In all three natural language tasks...

Capacity planning in a general supply chain with multiple contract types

Huang, Xin, 1978-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 150 leaves
Português
Relevância na Pesquisa
65.51%
In this thesis, we study capacity planning in a general supply chain that contains multiple products, processes, and resources. We consider situations with demand uncertainty, outsourcing contracts, and option contracts. We develop efficient and practical algorithms to address the following three questions: which suppliers should the manufacturer select, which types of contracts should it use, and how much capacity should it reserve. Through the model and algorithms, we study the properties of, and draw managerial insights about the optimal capacity planning strategy. First, we propose a model to study the single period capacity planning problem. We provide closed-form representations of the optimal capacity planning strategy for two special supply chain structures. We then develop a stochastic linear programming algorithm to solve the general single period problem and show that our algorithm outperforms the alternative algorithms by means of an empirical study. With the model and algorithm, we then study the effects of demand uncertainty, prices, common processes, and option contracts on the optimal capacity planning strategy. We conclude with a discussion on how to include lot size constraints into the model. Second, we develop a decomposition method for the single period capacity planning problem under the assumption that each process has only one dedicated resource. The algorithm provides both a feasible solution and an upper bound on the profit of the capacity planning problem. We test the effectiveness of the feasible solution and the tightness of the upper bound in the single period problem through a series of randomly generated test cases. The result shows that the algorithm performs fairly well with an average error of 1.48% on a set of test cases. Third...

Fast methods for inverse wave scattering problems

Lee, Jung Hoon, Ph. D. Massachusetts Institute of Technology
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 137 p.
Português
Relevância na Pesquisa
65.51%
Inverse wave scattering problems arise in many applications including computerized/diffraction tomography, seismology, diffraction/holographic grating design, object identification from radar singals, and semiconductor quality control. Efficient algorithms exist for some inverse wave scattering problems in the low- and high-frequency regime or with weak scatterers. However, inverse wave scattering problems in the resonance regime with strong scatterers still pose many challenges. This thesis proposes algorithms for inverse wave scattering problems in the resonance regime with strong scatterers. These problems are part of, for instance, grating design, object identification, and semiconductor quality control. The proposed methods are (a) a spectrally convergent Nyström method for periodic structures in 2-D; (b) a fast Jacobian approximation method accompanying a Nyström method; (c) a fast and accurate method for evaluating the potential integrals in the 3-D mixed-potential integral operator with the Rao-Wilton-Glisson basis function; and (d) optimization with parameterized reduced-order models. The Nyström method and the method to evaluate the potential integrals accelerate scattered field evaluations by solving integral equations efficiently. The Jacobian approximation method and optimization with parameterized reduced-order models efficiently couple algorithms to evaluate scattered fields due to a guess of the scatterer and optimization methods to improve the guess. The Nyström and the Jacobian approximation methods are used to identify the parameters characterizing a periodic dielectric grating in 2-D. The method to evaluate the potential integrals and optimization with parameterized reduced-order models are applied to the problem of identifying simple discrete geometries in 3-D.; by Jung Hoon Lee.; Thesis (Ph. D.)--Massachusetts Institute of Technology...

Language Instance Generation and Test Case Construction for NP-hard Problems

Sanchis, Laura A.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
65.51%
Ph.D. Thesis, Computer Science Dept., U. Rochester; Prof. Mark A. Fulk, thesis advisor; simultaneously published in the Technical Report series.; This dissertation deals with the construction and generation of language instances, and with the related problem of constructing test cases for the empirical testing of approximation algorithms for NP-hard problems. In the first part of the thesis some theoretical aspects of language instance generation are investigated, especially in relation to other areas of complexity theory. Generators and constructors are machines that output instances of a language having certain characteristics, such as length, as specified by the input. Various types of generating machines are defined and the language classes having such machines are classified. Of particular interest are the languages that have efficient (polynomial-time) generators. Although only NP languages may have polynomial-time generators, it is shown that determining whether or not all NP languages have polynomial-time generators is related to other open problems in complexity theory, and that even under the assumption that P does not equal NP, the question cannot be resolved using techniques that relativize. The need to generate or construct structures having certain properties comes up in many circumstances and applications. One of these is the construction of test cases for the empirical testing of algorithms. When testing approximation algorithms for NP-hard problems...

Distributed algorithms for self-disassembly in modular robots

Gilpin, Kyle W
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 226 p.
Português
Relevância na Pesquisa
75.52%
We developed a modular robotic system that behaves as programmable matter. Specifically, we designed, implemented, and tested a collection of robots that, starting from an amorphous arrangement, can be assembled into arbitrary shapes and then commanded to self-disassemble in an organized manner. The 28 modules in the system were implemented as 1.77-inch autonomous cubes that were able to connect to and communicate with their immediate neighbors. Two cooperating microprocessors controlled the modules' magnetic connection mechanisms and infrared communication interfaces. We developed algorithms for the distributed communication and control of the system which allowed the modules to perform localization and distribute shape information in an efficient manner. When assembled into a structure, the modules formed a system which could be virtually sculpted using a computer interface which we also designed. By employing the sculpting process, we were able to accurately control the final shape assumed by the structure. Unnecessary modules disconnected from the structure and fell away. The results of close to 200 experiments showed the that the algorithms operated as expected and were able to successfully control the distributed system. We were able to quickly form one...

Indexical grounding for a mobile robot; Semantic grounding in a natural language interface

Kehoe, Charles W. (Charles Ward)
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 27 p.; 1446546 bytes; 1445037 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
65.44%
We have outfitted a mobile research robot with several sensors and algorithms designed to facilitate small- and large-scale navigation and natural language interaction. We begin with a parser using a large, hand-crafted English grammar and lexicon. We then add a standard gradient navigation algorithm for local obstacle avoidance, and a line segment comparison algorithm for basic, high-performance location recognition. The result is a full end-to-end system for natural-language-driven, mobile robotics research. The theme of grounding-mapping linguistic references to the corresponding real-world entities-runs throughout our approach. After the parser simplifies linguistic symbols and structures, we must connect them to the basic concepts that they represent, and then to our system's specific sensor readings and motor commands, to make natural language interaction possible. Additionally, many of the symbols we must ground are indexicals with critical contextual dependencies. We must therefore handle the implicit context that spatial communication carries with it.; by Charles W. Kehoe.; Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.; Includes bibliographical references (p. 26-27).

Efficient integral equation based algorithms for parasitic extraction of interconnects with smooth or rough surface

Zhu, Zhenhai, 1970-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 198 p.; 8283586 bytes; 8308765 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
75.51%
This thesis describes a few efficient parasitic extraction algorithms based on integral equation methods. It has two parts. Part one describes the algorithms used in FastImp, a program for accurate analysis of wide-band electromagnetic effects in very complicated geometries of conductors. The program is based on a recently developed surface integral formulation and a Pre-corrected FFT accelerated iterative method, but includes a new piecewise quadrature panel integration scheme, a new scaling and preconditioning technique as well as a generalized grid interpolation and projection strategy. Computational results are given on a variety of integrated circuit interconnect structures to demonstrate that FastImp is robust and can accurately analyze very complicated geometries of conductors. Part two describes an efficient Stochastic Integral Equation (SIE) Method for computing the mean value and variance of the capacitance of interconnects with random surface roughness in O(Nlog2̂(N)) time. An ensemble average Green's function is used to account for the surface roughness. A second-order correction scheme is used to improve the accuracy. A sparsification technique based on the Hierarchical Matrix method is proposed to significantly reduce the computational cost. The SIE method avoids the time-consuming Monte Carlo simulations and the discretization of rough surfaces. Numerical experiments show that the results of the new method agree very well with those of Monte Carlo simulations.; by Zhenhai Zhu.; Thesis (Ph. D.)--Massachusetts Institute of Technology...

Power-efficient design of 16-bit mixed-operand multipliers

Pornpromlikit, Sataporn, 1979-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 53 p.; 2616726 bytes; 2621261 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
75.52%
Multiplication is an expensive and slow arithmetic operation, which plays an important role in many DSP algorithms. It usually lies in the critical-delay paths, having an effect on performance of the system as well as consuming large power. Consequently, significant improvements in both power and performance can be achieved in the overall DSP system by carefully designing and optimizing power and performance of the multiplier. This thesis explores several circuit-level techniques for power-efficiently designing multipliers, including supply voltage reduction, efficient multiplication algorithms, low power circuit logic styles, and transistor sizing using dynamic and static tuners. Based on these techniques, several 16-bit multipliers have been successfully designed and implemented in 0.13[micro]m CMOS technology at the supply voltage of 1.5V and 0.9V. The multipliers are modified to handle multiplications of two 16-bit operands in which each can be either signed magnitude or two's complement formats. Examining power-performance characteristics of these multipliers reveals that both array and tree structures are feasible solutions for designing 16-bit multipliers, and complementary CMOS and single-ended CPL-TG logics are promising candidates for power-efficient design. The appropriate choices of structures and logic styles depend on power and performance constraints of the particular design.; by Sataporn Pornpromlikit.; Thesis (M. Eng.)--Massachusetts Institute of Technology...

Full-wave algorithms for model order reduction and electromagnet analysis of impedance and scattering; New full-wave algorithms for model order reduction and electromagnet analysis of impedance and scattering

Klemas, Thomas J. (Thomas Jonas)
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 178 p.; 9142640 bytes; 9150107 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
75.56%
As technology advances and sophisticated electronic systems achieve ubiquity, the demand for thorough, efficient Electromagnetic (EM) analysis continues to rise. The prohibitive costs of constructing and maintaining measurement facilities and designing and buildin-l system prototypes has fueled even greater demand for Computational Electromagnetics (CEM). Today's CEM solvers can generate models that accurately characterize the EM behavior of an arbitrary structure presented for analysis. Two important applications for CEM are Scattering analysis of targets excited by EM waves and impedance modelling for the interconnect between the electronic components in Systems on Package (SoP) and Systems on Board (SoB). Often, the goal of analysis is to characterize behavior relative to parameters of interest. and EMI solvers can generate paralneter-depenldent models of the system. The complexity of structures has increased so much that solving the solver-generated models at numerous desired parameter-points is a daunting computational task. For example, using these models in a simulator would be infeasible.; (cont.) Instead, existing Model Order Reduction (MOR) algorithms can construct reduced order models (ROMs) that clharacterize the pararreter-dependent behavior of the original system. These existing methods are effective when the system of equations is linearly or weakly nonlinearly dependent on the parameters. When analyzing structures that are large compared to wavelengths of interest...

An agent-based approach to modeling electricity spot markets

Visudhiphan, Poonsaeng, 1973-
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 327 p.; 23559864 bytes; 23605219 bytes; application/pdf; application/pdf
Português
Relevância na Pesquisa
65.51%
(cont.) The model could also be used to analyze market factors (such as new market rules) and their effects on market price dynamics and market participants' behaviors, as well as to identify the "best" response action of one participant against the opponents' actions.; Current approaches used for modeling electricity spot markets are static oligopoly models that provide top-down analyses without considering dynamic interactions among market participants. This thesis presents an alternative model, an agent-based model, and uses it to analyze the markets under various conditions. These markets, in which the participants engage in sealed-bid auctions to sell and/or buy electricity regularly, are viewed as multiagent systems, or as repeated games, played by participants with incomplete information. To represent these market characteristics, the agent-based model is selected, consisting of several power-producing agents with non-uniform portfolios of generating units. These agents employ learning algorithms, including Auer et al. 's, softmax action selection, or Visudhiphan and IliC's model-based algorithms, in determining bid-supply functions from available information. The simulated outcomes from the agent-based model depend on the choice of non-uniform portfolios and on the learning algorithms that the agents employ. Model verifications against the actual markets are suggested; however...

Preservation and decomposition theorems for bounded degree structures

Harwath, Frederik; Heimberg, Lucas; Schweikardt, Nicole
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/11/2015 Português
Relevância na Pesquisa
65.56%
We provide elementary algorithms for two preservation theorems for first-order sentences (FO) on the class $\mathfrak{C}_d$ of all finite structures of degree at most $d$: For each FO-sentence that is preserved under extensions (homomorphisms) on $\mathfrak{C}_d$, a $\mathfrak{C}_d$-equivalent existential (existential-positive) FO-sentence can be constructed in 5-fold (4-fold) exponential time. This is complemented by lower bounds showing that a 3-fold exponential blow-up of the computed existential (existential-positive) sentence is unavoidable. Both algorithms can be extended (while maintaining the upper and lower bounds on their time complexity) to input first-order sentences with modulo $m$ counting quantifiers (FO+MOD$_m$). Furthermore, we show that for an input FO-formula, a $\mathfrak{C}_d$-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound.; Comment: 42 pages and 3 figures. This is the full version of: Frederik Harwath, Lucas Heimberg, and Nicole Schweikardt. Preservation and decomposition theorems for bounded degree structures. In Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) and the 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)...