Bipartite experiments have recently emerged as a focal point in causal inference. In these experiments, treatment is administered to one set of units, while outcomes of interest are gauged on a distinct set of units. Such experiments are especially valuable in scenarios where pronounced interference effects transpire between units on a bipartite network. For instance, in market experiments, designating treatment at the seller level and assessing outcomes at the buyer level (or vice-versa) can lead to causal models that more accurately reflect the inherent interference between buyers and sellers. Although bipartite experiments can enhance the precision of causal effect estimations in specific contexts, it's imperative to conduct the analysis judiciously to avoid introducing undue bias through the network. Drawing from the generalized propensity score literature, we demonstrate that it's feasible to achieve unbiased estimates of causal effects for bipartite experiments, given a conventional set of assumptions. Furthermore, we delve into the formulation of confidence sets with accurate coverage probabilities. By employing a bipartite graph from a publicly accessible dataset previously explored in bipartite experiment studies, we illustrate, via simulations, a notable reduction in bias and augmented coverage. / Statistics

Motivated by problems in logistics, image recognition, and statistics, we consider the server allocation problem. In this problem, we are given $k$ servers (with capacities) and $n$ requests, which are points in a metric space. A server serves a request by moving to the request location, and the goal is to serve all requests while minimizing the total movement of servers, subject to the constraint that the number of requests served by a server cannot exceed its capacity. When the server capacity is $1$, and for the Euclidean metric, the problem reduces to the Euclidean bipartite matching problem. When the capacity is $infty$, suppose we are also provided with the order in which requests are to be served, the problem is the $k$-first come first served routing problem. We also consider a generalization of the $k$-first come first served routing problem to the taxi allocation problem, where each request is associated with a pickup location, dropoff location, and pickup time, and the server's velocity is also given as input. We present new algorithms for the Euclidean bipartite matching problem, showing improvements over existing algorithms. In particular, for two point sets $A, B subset mathbb{R}^d$ with $|A| = |B| = n$ and dimension $d > 1$ being constant, we developed: begin{itemize} item A faster algorithm that computes an $varepsilon$-approximate minimum-cost perfect matching in $O(n(varepsilon^{-O(d^3)}loglog n + varepsilon^{-O(d)}log^4 nlog^5log n))$ time. This is an improvement over previous algorithms, which took $n(varepsilon^{-1}log n)^{Omega(d)}$ time. item An algorithm that boosts the accuracy of any $varepsilon$-additive approximation algorithm, achieving an expected additive error of $min{varepsilon, (dloglog n)w^*}$ from the optimal matching cost $w^*$ in $O(T(n, varepsilon/d)loglog n)$ time, where $T(n, varepsilon)$ is the time complexity of any given $eps$-additive approximation algorithm. end{itemize} For the $k$-first come first served routing problem, we present the following results. begin{itemize} item The online version of the $k$-first come first served routing problem is the celebrated $k$-server problem. The best-known online algorithm for this problem is the Work Function algorithm. We present a new implementation of the work function algorithm, where processing the $i$th request takes $O((i+k)^2)$ time, improving on the previous methods that take $Omega(k(i+k)^2)$ time. item For the offline setting, we show that the $k$-first come first served routing problem and the taxi allocation problem can be reduced to the minimum-cost bipartite matching problem. Using this reduction, begin{itemize} item we develop a time-based divide-and-conquer algorithm to obtain an optimal solution in $tilde{O}(kn^2)$ time, which can be further improved to $tilde{O}(kn)$ when the requests and servers are in two-dimensional Euclidean space, and, item we apply a recently presented geometric divide-and-conquer algorithm to obtain an optimal solution for the taxi routing problem in a two-dimensional Euclidean space. As a result, we obtain significant empirical performance improvements for the taxi allocation problem in a two-dimensional space where the cost of moving from one location to another is lower bounded by the Euclidean cost. end{itemize} end{itemize} / Doctor of Philosophy / In the server allocation problem, we are given n requests and k servers, both as points in a space. A server can serve a request by moving to the request location, and each request can be served by exactly one server. The objective is to optimize the allocation of servers to requests such that the total distance traveled by the servers is minimized. In this thesis, we present efficient algorithms for three specific problems in the server allocation problem framework. First, we consider the case when the servers are restricted to serving up to one request each. This problem reduces to the well-known minimum cost maximum cardinality bipartite matching problem. When the underlying distance is Euclidean, this problem is called the Euclidean bipartite matching problem. We present two efficient algorithms that improve the state-of-the-art for the Euclidean bipartite matching problem. Second, we consider the case when the servers can handle multiple requests. Assuming the requests are given as ordered sequences, a server can serve a subsequence of the request sequence. We devise two efficient algorithms for this problem and show empirical performance improvements on the New York Taxi data set. Third, we consider the scenario when the requests appear in an online fashion such that on the arrival of each request, a server must be allocated to it immediately and irrevocably. This problem is the celebrated k-server problem. The work function algorithm is an online algorithm that solves the k-server problem with the best-known competitive ratio. We present a new, faster implementation of the work function algorithm.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第25089号 / 理博第4996号 / 新制||理||1714(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 COLLINSBenoit Vincent Pierre, 教授 泉 正己, 准教授 山下 真由子 / 学位規則第4条第1項該当 / Doctor of Agricultural Science / Kyoto University / DFAM

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy of $S(n,m)$. The study of bipartite Ramsey numbers was initiated in the early 1970s by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel. The exact value of $r_{bip}(S(n,m);k)$ is only known for $n=m=1$ and all $k\ge2$. Here we prove that if $k=2$ and $n\ge m$, or $k\ge3$ and $n\ge 2m$, then \[ r_{bip}(S(n,m);k)=kn+1.\] For $k \geq 3$ and $m \leq n < 2m$, we prove that, \[\max\{kn + 1, (2k-4)m+1\} \leq r_{bip}(S(n,m) ; k) \leq \max\left\{ kn + 1, \left[2k - 1 - \frac{1}{2k} - O\left(\frac{1}{k^2}\right)\right]m + 1 \right \},\] where the lower bound is due to DeBiasio, Gy\'arf\'as, Krueger, Ruszink\'o, and S\'ark\"ozy in 2019.

Network alignment is the problem of finding a common subgraph between two graphs, and more generally <i>k </i>graphs. The results of network alignment are often used for information transfer, which makes it a powerful tool for deducing information or insight about networks. Network alignment is tightly related to the subgraph isomorphism problem which is known to be NP-hard, this makes the network alignment problem supremely hard in practice. Some algorithms have been devised to approach it via solving a form of a relaxed version of the NP-hard problem or by defining certain heuristic measures. These algorithms normally work well for problems when there is some form of prior known similarity between the nodes of the graphs to be aligned. The absence of such information makes the problem more challenging. In this scenario, these algorithms would often require much more time to finish executing, and even fail sometimes. The version of network alignment that this thesis tackles is the one when such prior similarity measures are absent. In this thesis, we address three versions of network alignment: (i) multimoal network alignment, (ii) standard pairwise network alignment, and (iii) multiple network alignment. A key common component of the algorithms presented in this thesis is exploiting a low rank structure in the network alignment problem and thus producing algorithms that run much faster than classic network alignment algorithms.

Clustering is the process in which data is differentiated, classified according to some criteria. As a result of partitioning process, data is grouped into clusters for specific purpose. In a social network, clustering of people is one of the most popular problems. Therefore, we mainly concentrated on finding an efficient algorithm for this problem. In our study, data is made up of two types of entities (e.g., people, groups vs. political issues, religious beliefs) and distinct from most previous works, signed weighted bipartite graphs are used to model relations among them. For the partitioning criterion, we use the strength of the opinions between the entities. Our main intention is to partition the data into k-clusters so that entities within clusters represent strong relationship. One such example from a political domain is the opinion of people on issues. Using the signed weights on the edges, these bipartite graphs can be partitioned into two or more clusters. In political domain, a cluster represents strong relationship among a group of people and a group of issues. After partitioning, each cluster in the result set contains like-minded people and advocated issues. Our work introduces a general mechanism for k-way partitioning of signed bipartite graphs. One of the great advantages of our thesis is that it does not require any preliminary information about the structure of the input dataset. The idea has been illustrated on real and randomly generated data and promising results have been shown.

在這篇論文中，我們針對2-連通的最大外平面圖而且是二分圖的圖形，討論 其容忍表示法，並找到它的所有禁止子圖H1、H2、H3、H4。 / In this thesis, we prove a 2-connected graph G which is maximal outerplanar and bipartite is a tolerance graph if and only if there is no induced subgraphs H1; H2; H3 and H4 of G.

Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree. 5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity 6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering. 7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ log log Δ factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.

We investigate here some aspects of cycle bases of undirected graphs that allow the iterative construction of all elementary cycles. We introduce the concept of quasi-robust bases as a generalization of the notion of robust bases and demonstrate that a certain class of bases of the complete bipartite graphs K m,n with m,n _> 5 is quasi-robust but not robust. We furthermore disprove a conjecture for cycle bases of Cartesian product graphs.

Microorganisms are all around us. Some of them even live in our body and are essential for our healthy being. Study of microbial communities based on their genetic content has become very popular with the development of new technologies, which enable easy reading of DNA or RNA. The key role of these studies is usually to characterize significant microbial patterns of an environment. However, currently used visualization tools have many drawbacks for such analyses. The subject of this thesis is to design a R/Bioconductor package for simple creation of bipartite graphs from microbial data. This type of visualization brings many advantages for microbiome analysis. Benefits of bipartite graphs are further demonstrated by analysis of main parameters affecting computer processing of microbial data.