Idea

Streaming and Matching Problems with Submodular Functions

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also been numerous works that study combinatorial problems with submodular objective functions. This is motivated by their natural diminishing returns property which is useful in real-world applications. The thesis at hand is concerned with the study of streaming and matching problems with submodular functions.Firstly, motivated by developing robust algorithms, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We study the maximum matching problem and cardinality constrained monotone submodular maximization. We show that even under this seemingly powerful adversary, it is possible to break the barrier of 1/2 for both these problems in the streaming setting. Our main result is a novel streaming algorithm that computes a 0.55-approximation for cardinality constrained monotone submodular maximization.In the second part of the thesis, we study the problem of matroid intersection in the semi-streaming setting. Our main result is a (2 + e)-approximate semi-streaming algorithm for weighted matroid inter- section improving upon the previous best guarantee of 4 + e. While our algorithm is based on the local ratio technique, its analysis differs from the related problem of weighted maximum matching and uses the concept of matroid kernels. We are also able to generalize our results to work for submodular functions by adapting ideas from a recent result by Levin and Wajc (SODA'21) on submodular maximization subject to matching constraints.Finally, we study the submodular Santa Claus problem in the restricted assignment case. The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function fi. The goal is to maximize mini fi(Si) where S1, . . . , Sm is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n1/2+e)-approximation algorithm. In the restricted assignment case, each player is given a set of desired resources Gi and the individual valuation functions are defined as fi(S)= f(SnGi). OurmainresultisaO(loglog(n))-approximation algorithm for the problem. Our proof is inspired by the approach of Bansal and Srividenko (STOC'06) to the Santa Claus problem. Com- pared to the more basic linear setting, the introduction of submodularity requires a much more involved analysis and several new ideas.

EPFL2022

Permanence and Persistence Conception, Construction and Conversion of Modern Cinema Theatres [1910-1939]

Joana de Almeida Gouveia Oliveira Alves

This work is based on the assumption that it is possible to achieve sustainable development by preserving the twentieth century heritage. Modern European cinemas were especially vulnerable to the passing of time: in a few decades buildings with tremendous socio-cultural importance became obsolete structures in cities. This research into cinema theatre design in Western Europe during the period 1910-1939 is based on articles on cinema design published in leading architectural periodicals, using the information they contain to trace the history of the cinemas which had the greatest influence on the development of this building type in Europe. Chapters II and III focus on the theoretical and technical approaches to cinema building and aim to synthesise the ideas discussed at the time. They represent a study of the emergence of cinema as an autonomous architectural programme and how this building type was developed. The final chapters concern the abandonment of cinema theatres, which has resulted in a number of public demonstrations calling for the function of these buildings as cultural venues to be maintained and for their physical conservation. Unlike the usual nostalgic approach, an objective study of the conversion processes for these buildings enables conversion patterns to be identified. A significant number of the buildings in the study were demolished or gutted as a result of speculative financial ventures, while others were reused. The ultimate purpose of this thesis is to understand the aspects on which the life cycle of a cinema theatre and its permanence in the urban fabric depend, even if it serves a different function.

EPFL2015

Three Essays on Methodologies for Dynamic Modeling of Emerging Socio-technical Systems

Mohammad Amin Dehdarian

Socio-technical energy transitions are long-term and major transformations in incumbent energy infrastructures. They include fundamental changes in technologies as well as institutions and social patterns. Transition studies are primarily focused on frameworks for analyzing the entire transition process by investigating the historical cases of transitions. A multi-phase approach to transition posits this process begins with a pre-development phase characterized by technological and institutional lock-ins, and resistance from incumbent actors. This period is critical for a forward-looking approach to transitions, since early developments shape path-dependent and irreversible processes leading to the emergence of new transition pathways. However, our understanding about the mechanisms and dynamics of this phase is still very limited. This is mainly due to lack of data, weak conceptualization and the necessity of developing new methods proper to deal with these limitations. This dissertation develops methodologies for investigating some complex questions arising in the pre-development phase, by focusing on the case of smart grid development. The first essay uses insights from modeling interventions in complex systems and builds a System Dynamics model to investigate the cost allocation problem of smart metering roll-out. The second essay takes ideas from Technological Innovation System approach and develops a method to analyze the emergence of spatial diversity in smart grid development by combining Social Network Analysis and Agent-Based Modeling. The third essay builds on ideas from network theory and evolutionary modeling to develop a method for identifying the main path of knowledge development and analyzing knowledge trajectories in smart grid initiatives.

EPFL2017

Le vide

Stephanie Bender

Today the question of how to work in the continuous contemporary urban landscape, is a big concern for urban development professionals. Still marked by the modern obsession to define the building forms, a vision influenced by the functionalist movement of the Thirties, these same professionals have lost their means of working sustainably in a contemporary city which is both continuous and fragmented, like an individualised collection of various materials and shapes without urban links, spreading out without limits in the overall landscape. In this chaos, an urban approach has appeared, changing the interest from the building to its landscape, from the built to the non-built, and above all from the filled to the void, and offers a new approach more adapted to the context of today's urban environment, capable of creating links with the non built, of offering new urban materials through the 'non urban', and generating public spaces in the presence of 'non-form' buildings. This approach, which here is called The void. New urban strategies, works with the 'non-materials' such as the landscape, the infrastructure or the programmes, and tries to meet the challenge of a new urbanism in the contemporary city. To understand this, the thesis will strive to explore the chronology of this idea through its different chapters. A 'prehistory' will provide an understanding of the origins of this, via its discoverers, pioneers and precursors and will present an astonishing picture of first attempts to define the urban environment via the void. The case of Melun-Senart, the urban strategy developed in 1987 by Rem Koolhaas and his Office for Metropolitan Architecture (OMA), considered as the starting point for this search and as the masterpiece of the Void approach, will demonstrate the extremely innovative phenomena which resulted from what it called by its author as the "Strategy of the void". Putting this into perspective in the work of Rem Koolhaas will reveal a dense web of projects and writings on, or with the void, which again reinforces the idea of its pertinence. The exploration of the artistic fields and parallel philosophies, will demonstrate the pre-existence of the 'void' concepts amongst the protagonists and will prove the huge influence that they had in the construction of this new urban idea for the architects and the urban planners, and in particular Koolhaas. Finally, other contemporary urban protagonists will illustrate through their projects and their writings, a variety of approaches for the void up to the present day. And right at the end, an experiment through the void projects of the author, will offer an introspective vision of the process. More than two decades after the 'Strategy of the void' this approach goes beyond the diagrammatic stage of a competition, confirming not only its pertinence, but also its ability to provide answers that are both varied and renewed to the extremely complex and confused situations that are to be found in today's urban environment. This new way of conceptualising the urban landscape by the void, the reference for the dense area of the historical city, is replaced by the informal void of the contemporary city considered as the very identity of this new continuous urbanism and shows itself ultimately to be the void. a new urban strategy.

EPFL2011

Finite Element Method on Riemann Surfaces and Applications to the Laplacian Spectrum

Marc Maintrot

The objective of this PhD thesis is the approximate computation of the solutions of the Spectral Problem associated with the Laplace operator on a compact Riemann surface without boundaries. A Riemann surface can be seen as a gluing of portions of the Hyperbolic Plane made with suitable conditions to obtain a 2 dimensional manifold. The solutions of the Spectral Problem associated with the Laplace operator are to be understood as the eigenfunctions defined on the surface and their corresponding eigenvalues. This work is separated into two parts: the first part describes the method used to approximate the eigenvalues and eigenfunctions, the second focuses on the design of a program to compute these approximations. The approximation method is inspired by the Finite Element Method (FEM), in that it relies on the variational expression of the Spectral Problem and the definition of a finite subspace of functions in which the approximated eigenvalues and eigenfunctions are computed. However, it differs from the FEM in that it removes the euclidian basis of the FEM and is invariant under the isometries of the Hyperbolic Plane. To ful fill this objective, we begin by geodesically triangulating the surface as regularly as possible. This hyperbolic triangulation allows us to de ne the finite subspace of functions by using the concept of barycentric coordinates associated with each vertex of the triangulation (idea introduced by Whitney and taken up by Dodziuk). We then prove that the approximated solutions convergence to the exact ones when the diameter of the triangulation decreases, as well as the order of convergence. The program is a practical application of the theoretical work and allows the computation of the approximated eigenfunctions and eigenvalues.

EPFL2012

Technological innovation strategy in natural resource based industries

Bettina Lynda Bastian

This thesis analyses innovation and technology strategy within a primary industry, notably the upstream oil and gas industry. Industries that exploit and produce finite natural resources are challenged by specific external risks that do not receive much attention from management literature otherwise, especially with regard to organizational innovation behaviour, and thus merit such research focus. On one hand, primary sector firms are confronted with exhaustible nature of finite natural resources. On the other hand, those finite natural resources are fixed to certain locations and companies have to operate in numerous countries in order to exploit resource deposits. In this context, they are often confronted with tremendous socio-political constraints that may have a negative impact on their businesses. This research work raises questions specific to natural resource based industries, notably (1) how can firms defend or even expand their competitive position when they are challenged by the depletion of their core resources? How can firms compensate for an exhaustible resource? (2) How do we evaluate contingencies like political risk for competitive advantage and what role does innovation play in this context? This dissertation takes the format of a "compilation thesis", in this case, three compiled articles. Within the first paper we focus on the resource based view (RBV), a central theoretical approach in management science, which explains how unique firm resources and capabilities contribute to value creation and lead to sustained competitive advantage. We1 apply the assumptions of RBV to the context of finite natural resources and ask if its analytical power is sufficient to explain competitive advantage of companies active in the primary sector, such as hydrocarbon and ore production. Paper 2 analyses how firms respond to geophysical constraints, such as natural resource depletion, and how these depletion issues affect organizational capability building and operational performance in terms of resource exploration and recovery. Paper 3 asks if political risk as external threat influences firm technology and innovation strategies. We find that time horizons of political risk play an important role and analyse why mid-and long term threats positively influence the development of technology and innovation strategies. The dissertation makes several important contributions. First, it contributes to our understanding of innovation and technology strategy within a natural resource based industry. Second, the idea that finite natural resources with their exhaustible nature are different than the "usual" resources investigated by RBV is novel. Third, the analysis also shows how RBV applies to natural resources extracting industries, and how RBV would gain in explicatory power if it was able to integrate factors like "geophysical constraints" and 'exposure to political risk' into the approach. Fourth, the thesis applies RBV and capability approaches to the specific context of primary industries, which is important as it helps to extend the frameworks' usefulness. Fifth, the current thesis combines political risk theory and research on innovation and technology management, and answers why political risk influences firm strategies, differentiation, and entry into new fields. ______________________________ 1 I am going to use the personal pronoun "we" to refer to first person's actions or opinions in this paper. I do so because I want to acknowledge the contributory effort of all who provided ideas and support. Nevertheless, any errors and omissions are completely my own responsibility.

EPFL2009

The research program of Stochastic Deformation (with a view toward Geometric Mechanics)

This is an overview of a program of stochastic deformation of the mathematical tools of classical mechanics, in the Lagrangian and Hamiltonian approaches. It can also be regarded as a stochastic version of Geometric Mechanics.The main idea is to construct well defined probability measures strongly inspired by Feynman Path integral method in Quantum Mechanics. In contrast with other approaches, this deformation preserves the invariance under time reversal of the underlying classical (conservative) dynamical systems.

2012

Les mathématiques financières robustes, le maritime et les FFA

Jérôme Reboulleau

Powerful mathematical tools have been developed for trading in stocks and bonds, but other markets that are equally important for the globalized world have to some extent been neglected. We decided to study the shipping market as an new area of development in mathematical finance. The market in shipping derivatives (FFA and FOSVA) has only been developed after 2000 and now exhibits impressive growth. Financial actors have entered the field, but it is still largely undiscovered by institutional investors. The first part of the work was to identify the characteristics of the market in shipping, i.e. the segmentation and the volatility. Because the shipping business is old-fashioned, even the leading actors on the world stage (ship owners and banks) are using macro-economic models to forecast the rates. If the macro-economic models are logical and make sense, they fail to predict. For example, the factor port congestion has been much cited during the last few years, but it is clearly very difficult to control and is simply an indicator of traffic. From our own experience it appears that most ship owners are in fact market driven and rather bad at anticipating trends. Due to their ability to capture large moves, we chose to consider Lévy processes for the underlying price process. Compared with the macro-economic approach, the main advantage is the uniform and systematic structure this imposed on the models. We get in each case a favorable result for our technology and a gain in forecasting accuracy of around 10% depending on the maturity. The global distribution is more effectively modelled and the tails of the distribution are particularly well represented. This model can be used to forecast the market but also to evaluate the risk, for example, by computing the VaR. An important limitation is the non-robustness in the estimation of the Lévy processes. The use of robust estimators reinforces the information obtained from the observed data. Because maximum likelihood estimation is not easy to compute with complex processes, we only consider some very general robust score functions to manage the technical problems. Two new class of robust estimators are suggested. These are based on the work of F. Hampel ([29]) and P. Huber ([30]) using influence functions. The main idea is to bound the maximum likelihood score function. By doing this a bias is created in the parameters estimation, which can be corrected by using a modification of the following type and as proposed by F. Hampel. The procedure for finding a robust estimating equation is thus decomposed into two consecutive steps : Subtract the bias correction and then Bound the score function. In the case of complex Lévy processes, the bias correction is difficult to compute and generally unknown. We have developed a pragmatic solution by inverting the Hampel's procedure. Bound the score function and then Correct for the bias. The price is a loss of the theoretical properties of our estimators, besides the procedure converges to maximum likelihood estimate. A second solution to for achieving robust estimation is presented. It considers the limiting case when the upper and lower bounds tend to zero and leads to B-robust estimators. Because of the complexity of the Lévy distributions, this leads to identification problems.

EPFL2008

Technological innovation and economic transformation: A method for contextual analysis

Heidi Christina Gautschi

The underlying theme of our project is that society in its quest for order in an inherently chaotic natural setting tends to think about technological innovation much too narrowly, and this causes at least two kinds of problems. The first is the narrow attitude of the naysayer—one who too quickly asserts that, whatever it is, it cannot be done. Any aspiring innovator can recount the times that an idea has run headlong into a listing of reasons why it would not work. The second problem is the dual of the first. It is the narrow attitude of the visionary, who would be fixated only on achieving the aim of a single idea without acknowledging its connections to other facets of life in the context of the moment. In this project, we seek to strike a balance between retrospective and contemporary critique to encourage careful consideration of the specific benefits to society any given technology has the potential to deliver. We would argue that in almost every case, a technology whose sponsors have succeeded in building the case for its societal benefit must also be evaluated critically in terms of the associated adjustments that certain groups would be impelled to make.

Palgrave Macmillan2016