The Macroscopic Fundamental Diagram (MFD) is a diagram that presents a relationship between the average flow (production) and the average density in an urban network. Ever since the existence of low scatter MFD in urban road network was verified, significant efforts have been made to describe the MFD quantitatively. Due to the complexity of the traffic environment in urban networks, an accurate and explicit expression for the MFD is not yet developed and many recent research efforts for MFD rely on computer simulations. On a single corridor, an analytical approximation model for the MFD exists. However, this thesis expanded this theory in two directions. First, we specialize the method for models with equal road length on the corridor, which greatly reduces the complexity of the method. We introduce the adoption of seven straight cuts in approximation. Computer simulations are conducted and show a high compatibility with the approximated results. However the analytical approximation can only be applied with the assumption of constant circulating vehicles in the system without turnings and endogenous traffics. Secondly, we show that turnings and endogenous traffic can bring various impact on the shape of the MFD, the capacity, the critical density, the variance in density and cause a phenomenon of clustered traffic status along the MFD curve. Furthermore, the simulation using stochastic variables reveals that the variance in turning rates and endogenous traffic don’t have significant impact on the MFD. This discovery enables studies to focus on scenarios with deterministic parameters for those factors. While traditional objective of engineering for network is to maximize capacity and widen the range for the maximum capacity, our results indicate that traffic stability at the maximum performance is poor if the system does not stay constantly in equilibrium status. This thesis provides insights into the factors that affect the shape of the MFD by analytical approximation and simulation.

An α-approximation algorithm is an algorithm guaranteed to output a solutionthat is within an α ratio of the optimal solution. We are interested in thefollowing question: Given an NP-hard optimization problem, what is the bestapproximation guarantee that any polynomial time algorithm could achieve? We mostly focus on studying the approximability of two classes of NP-hardproblems: Constraint Satisfaction Problems (CSPs) and Computational Learning Problems. For CSPs, we mainly study the approximability of MAX CUT, MAX 3-CSP,MAX 2-LINR, VERTEX-PRICING, as well as serval variants of the UNIQUEGAMES.• The problem of MAX CUT is to find a partition of a graph so as to maximizethe number of edges between the two partitions. Assuming theUnique Games Conjecture, we give a complete characterization of the approximationcurve of the MAX CUT problem: for every optimum value ofthe instance, we show that certain SDP algorithm with RPR2 roundingalways achieve the optimal approximation curve.• The input to a 3-CSP is a set of Boolean constraints such that each constraintcontains at most 3 Boolean variables. The goal is to find an assignmentto these variables to maximize the number of satisfied constraints.We are interested in the case when a 3-CSP is satisfiable, i.e.,there does exist an assignment that satisfies every constraint. Assumingthe d-to-1 conjecture (a variant of the Unique Games Conjecture), weprove that it is NP-hard to give a better than 5/8-approximation for theproblem. Such a result matches a SDP algorithm by Zwick which givesa 5/8-approximation problem for satisfiable 3-CSP. In addition, our resultalso conditionally resolves a fundamental open problem in PCP theory onthe optimal soundness for a 3-query nonadaptive PCP system for NP withperfect completeness.• The problem of MAX 2-LINZ involves a linear systems of integer equations;these equations are so simple such that each equation contains atmost 2 variables. The goal is to find an assignment to the variables so asto maximize the total number of satisfied equations. It is a natural generalizationof the Unique Games Conjecture which address the hardness ofthe same equation systems over finite fields. We show that assuming theUnique Games Conjecture, for a MAX 2-LINZ instance, even that thereexists a solution that satisfies 1−ε of the equations, it is NP-hard to findone that satisfies ² of the equations for any ε > 0.

In the first part of this thesis, we present the first non-trivial small value estimate that applies to an algebraic group of dimension 2 and which involves large sets of points. The algebraic group that we consider is the product ℂ× ℂ*, of the additive group ℂ by the multiplicative group ℂ*. Our main result assumes the existence of a sequence (PD)D ≥1 of non-zero polynomials in ℤ [X1, X2] taking small absolute values at many translates of a fixed point (ξ, η) in ℂ × ℂ* by consecutive multiples of a rational point (r, s) ∈ (ℚ*)2 with s = ±1. Under precise conditions on the size of the coefficients of the polynomials PD, the number of translates of (ξ, η) and the absolute values of the polynomials PD at these points, we conclude that both ξ and η are algebraic over ℚ. We also show that the conditions that we impose are close from being best possible upon comparing them with what can be achieved through an application of Dirichlet’s box principle. In the second part of the thesis, we consider points of the form θ = (1,θ1 , . . . ,θd-1 ,ξ) where {1,θ1 , . . . ,θd-1 } is a basis of a real number field K of degree d ≥ 2 over ℚ and where ξ is a real number not in K. Our main results provide sharp upper bounds for the uniform exponent of approximation to θ by rational points, denoted λ ̂(θ), and for its dual uniform exponent of approximation, denoted τ ̂(θ). For d = 2, these estimates are best possible thanks to recent work of Roy. We do not know if they are best possible for other values of d. However, in Chapter 2, we provide additional information about rational approximations to such a point θ assuming that its exponent λ ̂(θ) achieves our upper bound. In the course of the proofs, we introduce new constructions which are interesting by themselves and should be useful for future research.

No description available.

Most combinatorial optimization problems are NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to the optimal, have become a rich field of study. One successful method for designing approx- imation algorithms has been to model the optimization problem as an integer program and then using its polynomial time solvable linear programming relaxation for the design and analysis of such algorithms. Such a technique is called the LP-based technique. In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems using LP-based techniques as our main tool. Connectivity Problems: We study the Steiner tree problem and devise new linear pro- gramming relaxations for the problem. We show an equivalence of our relaxation with the well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class of graphs called quasi-bipartite graphs, we improve the best known upper bound on the integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation algorithms for the Steiner tree problem on quasi-bipartite graphs. Allocation Problems: We study the budgeted al location problem of allocating a set of indivisible items to a set of agents who bid on it but possess a hard budget constraint more than which they are unwilling to pay. This problem is a special case of submodular welfare maximization. We use a natural LP relaxation for the problem and improve the best known approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox- imability factor of the problem to 15/16 and use our techniques to show inapproximability results for many other allocation problems. We also study online allocation problems where the set of items are unknown and appear one at a time. Under some necessary assumptions we provide online algorithms for many problems which attain the (almost) optimal competitive ratio. Both these works have applications in the area of budgeted auctions, the most famous of which are the sponsored search auctions hosted by search engines on the Internet. Design Problems: We formally define and study design problems which asks how the weights of an input instance can be designed, so that the minimum (or maximum) of a certain function of the input can be maximized (respectively, minimized). We show if the function can be approximated to any factor $alpha$, then the optimum design can be approximated to the same factor. We also show that (max-min) design problems are dual to packing problems. We use the framework developed by our study of design problems to obtain results about fraction- ally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte about packing spanning trees.

The purpose of the research presented here is twofold. The first component explores the probabilistic interpretation of Stein’s method, as introduced in Barbour (1988). This is done in the setting of random variable approximations. This probabilistic method, where the Stein equation is interpreted in terms of the generator of an underlying birth and death process having equilibrium distribution equal to that of the approximant, provides a natural explanation of why Stein’s method works. An open problem has been to use this generator approach to obtain bounds on the differences of the solution to the Stein equation. Uniform bounds on these differences produce Stein “magic” factors, which control the bounds. With the choice of unit per capita death rate for the birth and death process, we are able to produce a result giving a new Stein factor bound, which applies to a selection of distributions. The proof is via a probabilistic approach, and we also include a probabilistic proof of a Stein factor bound from Barbour, Holst and Janson (1992). These results generalise the work of Xia (1999), which applies to the Poisson distribution with unit per capita death rate. (For complete abstract open document)

L'étude de la distribution des points rationnels sur les variétés algébriques est un sujet classique de la géométrie diophantienne. Le programme proposé par V. Batyrev et Y. Manin dans des années 90 donne une prédiction sur l'ordre de croissance tandis que sa version ultérieure dûe à E. Peyre conjecture l'existence d'une distribution globale. Dans cette thèse nous nous proposons une étude de la distribution locale des points rationnels de hauteur bornée sur les variétés algébriques. Ceci envisage une description plus fine que celle globale en dénombrant les points le plus proche d'un point fixé. Nous nous plaçons sur le cadre récent du travail de D. McKinnon et M. Roth qui met en évidence que la géométrie de la variété gouverne l'approximation diophantienne sur elle et nous reprenons les résultats de S. Pagelot. L'ordre de croissance espéré et l'existence d'une mesure asymptotique sur certaines surfaces toriques sont démontrés, alors que démontrons-nous un résultat totalement différent pour une autre surface sur laquelle il n'y pas de mesure asymptotique et les meilleurs approximants génériques s'obtiennent sur des courbes rationnelles nodales. Ces deux phénomènes sont de nature radicalement différente au point de vu de l'approximation diophantienne. / The study of the distribution of rational points on algebraic varieties is a classic subject of Diophantine geometry. The program proposed by V. Batyrev and Y. Manin in the 1990s gives a prediction on the order of growth whereas its later version due to E. Peyre conjectures the existence of a global distribution. In this thesis we propose a study of the local distribution of rational points of bounded height on algebraic manifolds. This aims at giving a description finer than the global one by counting the points closest to a fixed point. We set ourselves on the recent framework of the work of D. McKinnon and M. Roth who prefers that the geometry of the variety governs the Diophantine approximation on it and we take up the results of S. Pagelot. The expected order of growth and the existence of an asymptotic measure on some toric surfaces are demonstrated, while we demonstrate a totally different result for another surface on which there is no asymptotic measure and the best generic approximates are obtained on nodal rational curves. These two phenomena are of a radically different nature from the point of view of the Diophantine approximation.

Dans la thèse on introduit et on étudie une généralisation spatiale sur $\R^d$ du quantile réel usuel sous la forme d'une surface quantile via des formes $\phi$ et d'un point d'observation $O$. Notre point de départ est de simplement admettre la subjectivité due à l'absence de relation d'ordre totale dans $\R^d$ et donc de développer une vision locale et directionnelle des données. Ainsi, les observations seront ordonnées du point de vue d'un observateur se trouvant à un point $O \in \R^d$. Dans le chapitre 2, on introduit la notion du quantile vue d'un observateur $O$ dans la direction $u \in \Sd$ et de niveau $\alpha$ via des des demi-espaces orthogonaux à chaque direction d'observation. Ce choix de classe implique que les résultats de convergence ne dépendent pas du choix de $O$. Sous des hypothèses minimales de régularité, l'ensemble des points quantile vue de $O$ définit une surface fermée. Sous hypothèses minimales, on établit pour les surfaces quantile empiriques associées les théorèmes limites uniformément en le niveau de quantile et la direction d'observation, avec vitesses asymptotiques et bornes d'approximation non-asymptotiques. Principalement la LGNU, la LLI, le TCLU, le principe d'invariance fort uniforme puis enfin l'approximation du type Bahadur-Kiefer uniforme, et avec vitesse d'approximation. Dans le chapitre 3, on étend les résultats du chapitre précédent au cas où les formes $\phi$ sont prises dans une classe plus générale (fonctions, surfaces, projections géodésiques, etc) que des demi-espaces qui correspondent à des projections orthogonales par direction. Dans ce cadre plus général, les résultats dépendent fortement du choix de $O$, et c'est ce qui permet de tirer des interprétations statistiques. Dans le chapitre 4, des conséquences méthodologiques en statistique inférentielle sont tirées. Tout d'abord on introduit une nouvelle notion de champ de profondeurs directionnelles baptisée champ d'altitude. Ensuite, on définit une notion de distance entre lois de probabilité, basée sur la comparaison des deux collections de surfaces quantile du type Gini-Lorrentz. La convergence avec vitesse des mesures empiriques pour cette distance quantile, permet de construire différents tests en contrôlant leurs niveaux et leurs puissances. Enfin, on donne une version des résultats dans le cas où une information auxiliaire est disponible sur une ou plusieurs coordonnées sous la forme de la connaissance exacte de la loi sur une partition finie. / The main issue of the thesis is the development of spatial generalizations on $\R^d$ of the usual real quantile. Facing the usual fact that $\R^d$ is not naturally ordered, our idea is to simply admit subjectivity and thus to define a local viewpoint rather than a global one, anchored at some point of reference $O$ and arbitrary shape $\phi$ with the motivation of crossing information gathered by changing viewpoint $O$, shape $\phi$ and $\alpha$-th order of quantile. In Chapter 2, we study the spatial quantile points seen from an observer $O$ in a direction $u \in \Sd$ of level $\alpha$ through the class of the half-spaces orthogonal to the direction $u$. This choice implies that the convergence theorems do not depend on the choice of $O$. Under minimal regularity assumptions, the set of all quantile points seen from $O$ is a closed surface. Under minimal assumptions, we establish for the associated empirical quantile surfaces the convergence theorems uniformly on the quantile level and the observation direction with the asymptotic speed and non-asymptotic bounds of approximation. Mainly, we establish the ULLN, the ULIL, the UCLT, the uniform strong invariance principle and finally the Bahadur-Kiefer type embedding, with the approximation speed rate. In Chapter 3, all the results of the previous chapter are extended to the case where the shapes $ \phi $ are taken in a class more general (functions, surfaces, geodesic projections, etc) than orthogonal projections (half-spaces). In this general setting, the results depend strongly on the choice of $ O $. It is this dependence which permit to draw statistical interpretations: modes detection, mass localization, etc. In Chapter 4, some methodological consequences in inferential statistics are drawn. First we introduce a new concept of directional depth fields called altitude fields. In a second application is defined a new distances between probability distributions, based on the comparison of two collections of quantile surfaces, which are indexes of the type Gini-Lorrentz. The convergence with speed of the empirical quantile measures for these distances, can build different tests with control of their level and their power. A third use of the quantile surfaces is for the case where $ \alpha = 1/2$. Finally, we give a version of our theorems in the case where auxiliary information is available on one or more coordinates of the random variable. By assuming known the probability of the elements of a finite partition, the asymptotic variance of the limiting process decreases and the simulations with few points clearly shows the reframe of the estimated surfaces to the real ones.

O objetivo desse trabalho é o estudo dos operadores p-compactos e da propriedade de p-aproximação. Estes conceitos estão relacionados a importantes resultados de A. Gröthendieck sobre compacidade e a propriedade de aproximação que foram generalizados em [21] e estudados em [3], [6] e [7]. / The purpose of this work is the study of p-compact operators and the p-approximation property. These concepts are connected with important results by A. Gröthendieck about compactness and approximation property that were generalized in [21] and studied in [3], [6] and [7].

In the first part of this thesis, we present the first non-trivial small value estimate that applies to an algebraic group of dimension 2 and which involves large sets of points. The algebraic group that we consider is the product ℂ× ℂ*, of the additive group ℂ by the multiplicative group ℂ*. Our main result assumes the existence of a sequence (PD)D ≥1 of non-zero polynomials in ℤ [X1, X2] taking small absolute values at many translates of a fixed point (ξ, η) in ℂ × ℂ* by consecutive multiples of a rational point (r, s) ∈ (ℚ*)2 with s = ±1. Under precise conditions on the size of the coefficients of the polynomials PD, the number of translates of (ξ, η) and the absolute values of the polynomials PD at these points, we conclude that both ξ and η are algebraic over ℚ. We also show that the conditions that we impose are close from being best possible upon comparing them with what can be achieved through an application of Dirichlet’s box principle. In the second part of the thesis, we consider points of the form θ = (1,θ1 , . . . ,θd-1 ,ξ) where {1,θ1 , . . . ,θd-1 } is a basis of a real number field K of degree d ≥ 2 over ℚ and where ξ is a real number not in K. Our main results provide sharp upper bounds for the uniform exponent of approximation to θ by rational points, denoted λ ̂(θ), and for its dual uniform exponent of approximation, denoted τ ̂(θ). For d = 2, these estimates are best possible thanks to recent work of Roy. We do not know if they are best possible for other values of d. However, in Chapter 2, we provide additional information about rational approximations to such a point θ assuming that its exponent λ ̂(θ) achieves our upper bound. In the course of the proofs, we introduce new constructions which are interesting by themselves and should be useful for future research.