## 数学代写|组合优化代写Combinatorial optimization代考|CSC205

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Polyhedra and Linear Programming

Definition 1. Let $x_1, x_2, \ldots, x_m$ be points in $\mathbb{R}^n$. Let $x=\sum_{i=1}^m \lambda_i x_i$, where each $\lambda_i \in \mathbb{R}, 1 \leq i \leq m$ is a scalar. Then, $x$ is said to be a(n)

1. Linear combination (of $x_i, 1 \leq i \leq m$ ) for arbitrary scalars $\lambda_i$.
2. Affine combination if $\sum_i \lambda_i=1$.
3. Conical combination if $\lambda_i \geq 0$.
4. Convex combination if $\sum \lambda_i=1$ and $\lambda_i \geq 0$ (affine and also canonical).
In the following definitions and propositions, unless otherwise stated, it will be assumed that $x_1, x_2, \ldots, x_m$ are points in $\mathbb{R}^n$ and $\lambda_1, \lambda_2, \ldots, \lambda_m$ are scalars in $\mathbb{R}$.
Definition 2. $x_1, x_2, \ldots, x_m$ are said to be linearly independent if $\sum_{i=1}^m \lambda_i x_i=0 \Rightarrow \forall i \in[m] \lambda_i=0$.
Definition 3. $x_1, x_2, \ldots, x_m$ are said to be affinely independent if the vectors $\left(x_i-x_1\right), i=2, \ldots, m$ are linearly independent, or equivalently if $\sum_{i=1}^m \lambda_i x_i=0$ and $\sum_{i=1}^m \lambda_i=0 \Rightarrow \forall i \in[m] \lambda_i=0$.
The following proposition is easy to check and the proof is left as an exercise to the reader.
Proposition 4. $x_1, x_2, \ldots, x_m$ are affinely independent if and only if the vectors $\left(\begin{array}{c}x_i \ 1\end{array}\right), i=1,2, \ldots, m$, are linearly independent in $\mathbb{R}^{m+1}$.

A set $X \subseteq \mathbb{R}^n$ is said to be a(n) subspace [affine set, cone set, convex set] if it is closed under linear [affine, conical, convex] combinations. Note that an affine set is a translation of a subspace. Given $X \subseteq$ $\mathbb{R}^n$, we let $\operatorname{Span}(X), \operatorname{Af}(X)$, Cone $(X)$, and Convex $(X)$ denote the closures of $X$ under linear, affine, conical, and convex combinations, respectively. To get an intuitive feel of the above definitions, see Figure 1.

## 数学代写|组合优化代写Combinatorial optimization代考|Fourier-Motzkin Elimination

Let $P={x \mid A x \leq b} \subseteq \mathbb{R}^n$ be a polyhedron. For $k$ in $[n]$,
we let $P^k=\left{\left(x_1, \ldots, x_{k-1}, x_{k+1}, \ldots, x_n\right) \mid\left(x_1, x_2, \ldots, x_n\right) \in P\right}$ be the projection of $P$ along the $x_k$-axis.
Theorem 13. $P^k$ is a polyhedron.
Proof. We derive a set of inequalities that describe $P^k$. We do this by considering the inequalities in $A x \leq b$ and eliminating the variables $x_k$ as follows. Partition the inequalities in $A x \leq b$ into three sets:
$$S^{+}=\left{i \in[m] \mid a_{i k}>0\right}, S^{-}=\left{i \in[m] \mid a_{i k}<0\right}, \text { and } S^0=\left{i \in[m] \mid a_{i k}=0\right} .$$
Define a new set of inequalities consisting of $S_0$ and one new inequality for each pair $(i, \ell)$ in $S^{+} \times S^{-}$:
$$a_{i k}\left(\sum_{j=1}^n a_{\ell j} x_j\right)-a_{\ell k}\left(\sum_{j=1}^n a_{i j} x_j\right) \leq a_{i k} b_{\ell}-a_{\ell k} b_i .$$
Note that the combined inequality does not have $x_k$. We now have a total of $\left|S^0\right|+\left|S^{+}\right|\left|S^{-}\right|$new inequalities. Let $P^{\prime}=\left{x^{\prime} \in \mathbb{R}^{n-1} \mid A^{\prime} x^{\prime} \leq b^{\prime}\right}$ where $A^{\prime} x^{\prime} \leq b^{\prime}$ is the new system of inequalities in variables $x_1, x_2, \ldots, x_{k-1}, x_{k+1}, \ldots, x_n$. We prove the theorem by showing that $P^k=P^{\prime}$.

We first show the easier direction: $P^k \subseteq P^{\prime}$. Consider any point $z \in P^k$. By definition of $P^k$, there exists $x \in P$ such that $A x \leq b$ and $x$ ‘s projection along $x_k$-axis is $z$. It is easy to see that $z$ satisfies the new system since the new one was obtained in a way oblivious to $x_k$, the real value of $x$ ‘s $k_{\text {th }}$ coordinate.
We now show that $P^{\prime} \subseteq P^k$. Without loss of generality, assume $k=1$. Consider any $x^{\prime}=\left(x_2, x_3, \ldots, x_n\right) \in$ $P^{\prime}$. We want to show that there exists $x_1 \in \mathbb{R}$ such that $A x \leq b$, where $x=\left(x_1, x_2, \ldots, x_n\right)$. For simple notation, define $C_i=b_i-\sum_{j=2}^n a_{i j} x_j$ for $i \in[m]$. Note that $A x \leq b$ can be rewritten as
$$a_{i 1} x_1 \leq C_i, \forall i \in[m] .$$
Observe that $x$ satisfies all inequalities consisting of $S^0$, since the new system as well includes those constraints. Thus we can refine our goal to show
$$\begin{array}{ll} \exists x_1 \text { s.t. } \quad & a_{i 1} x_1 \leq C_i, \forall i \in S^{+} \cup S^{-} . \ \Leftrightarrow \quad \max {\ell \in S^{-}} \frac{C{\ell}}{a_{\ell 1}} \leq x_1 \leq \min {i \in S^{+}} \frac{C_i}{a{i 1}} . \end{array}$$

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Polyhedra and Linear Programming

1. 线性组合 (的 $x_i, 1 \leq i \leq m$ ) 对于任意标量 $\lambda_i$.
2. 仿射组合如果 $\sum_i \lambda_i=1$.
3. 锥形组合如果 $\lambda_i \geq 0$.
4. 凸组合如果 $\sum \lambda_i=1$ 和 $\lambda_i \geq 0$ (仿射和规范)。
在以下定义和命题中，除非另有说明，否则将假定 $x_1, x_2, \ldots, x_m$ 是点在 $\mathbb{R}^n$ 和 $\lambda_1, \lambda_2, \ldots, \lambda_m$ 是 标量在 $\mathbb{R}$.
定义 $2 。 x_1, x_2, \ldots, x_m$ 被称为线性独立的如果 $\sum_{i=1}^m \lambda_i x_i=0 \Rightarrow \forall i \in[m] \lambda_i=0$.
定义 3。 $x_1, x_2, \ldots, x_m$ 如果向量是仿射独立的 $\left(x_i-x_1\right), i=2, \ldots, m$ 是线性独立的，或者等 效地如果 $\sum_{i=1}^m \lambda_i x_i=0$ 和 $\sum_{i=1}^m \lambda_i=0 \Rightarrow \forall i \in[m] \lambda_i=0$.
下面的命题很容易检验，证明留给读者作为练习。
命题 4 。 $x_1, x_2, \ldots, x_m$ 仿射独立当且仅当向量 $\left(x_i 1\right), i=1,2, \ldots, m$, 是线性独立的 $\mathbb{R}^{m+1}$.
一套 $X \subseteq \mathbb{R}^n$ 如果它在线性 [仿射、圆雉、凸] 组合下闭合，则称其为 $a(n)$ 子空间 [仿射集、锥集、凸 集]。请注意，仿射集是子空间的平移。鉴于 $X \subseteq \mathbb{R}^n$ ，我们让Span $(X), \operatorname{Af}(X)$ ，圆锥体 $(X)$ ，和凸 $(X)$ 表示闭包 $X$ 分别在线性、仿射、圆锥和凸组合下。要直观地感受上述定义，请参见图 1。

## 数学代写|组合优化代写Combinatorial optimization代考|Fourier-Motzkin Elimination

$$a_{i k}\left(\sum_{j=1}^n a_{\ell j} x_j\right)-a_{\ell k}\left(\sum_{j=1}^n a_{i j} x_j\right) \leq a_{i k} b_{\ell}-a_{\ell k} b_i .$$

$C_i=b_i-\sum_{j=2}^n a_{i j} x_j$ 为了 $i \in[m]$. 注意 $A x \leq b$ 可以改写为
$$a_{i 1} x_1 \leq C_i, \forall i \in[m] .$$

$$\exists x_1 \text { s.t. } \quad a_{i 1} x_1 \leq C_i, \forall i \in S^{+} \cup S^{-} . \Leftrightarrow \quad \max \ell \in S^{-} \frac{C \ell}{a_{\ell 1}} \leq x_1 \leq \min i \in S^{+} \frac{C_i}{a i 1} \text {. }$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|APM6664

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Bipartite Matchings

Many of you have seen bipartite matchings reduced to flow. We can also treat them independently. Let $G=(X \cup Y, E)$ be a bipartite graph with bipartition given by $X, Y$. Recall that $M \subseteq E$ is a matching in a graph if no vertex in $G$ is incident to more than one edge in $M$.

A vertex cover in $G=(V, E)$ is a subset of vertices $S \subseteq V$ such that for each edge $u v \in E, u$ or $v$ is in $S$. In other words, $S$ covers all edges. We use $\nu(G)$ to indicate the cardinality of a maximum matching in $G$ and $\tau(G)$ for the cardinality of a minimum vertex cover in $G$.
Proposition 3 For every $G, \nu(G) \leq \tau(G)$.
In bipartite graphs, one has the following theorem.
Theorem 4 (König’s Theorem) If $G$ is bipartite then $\nu(G)=\tau(G)$.
The above proves that the max matching and min vertex problems (decision versions) in bipartite graphs are both in NP $\cap$ coNP . (Note that the vertex cover problem is NP -hard in general graphs.) We therefore expect a polynomial time algorithm for $\nu(G)$ and $\tau(G)$ in bipartite graphs. As you know, one can reduce matching in bipartite graphs to maxflow and König’s theorem follows from the maxflow-mincut theorem. One can also obtain a polynomial time augmenting path algorithm for matching in bipartite graphs (implicitly a maxflow algorithm) that proves König’s theorem algorithmically.

We now look at the polyhedral aspect. We can write a simple LP as a relaxation for the maximum matching in a graph $G$.
\begin{aligned} \max & \sum_{e \in E} x(e) \ \sum_{-G \delta(*)} x(e) & \leq 1 \quad \forall u \in V \ x(e) & \geq 0 \quad \forall e \in E \end{aligned}
For bipartite graphs the above LP and its dual have integral solutions since the constraint matrix is TUM. One can easily derive König’s theorem and a polynomial time algorithm from this. One also obtains a polynomial time algorithm for weighted matching (assignment problem).

## 数学代写|组合优化代写Combinatorial optimization代考|Tutte-Berge formula

We will prove the easy direction for now, i.e.,
$$\nu(G) \leq \frac{1}{2}(|V|+|U|-o(G-U)) \quad \forall U \subseteq V$$
To see this, the number of unmatched vertices is at least $o(G-U)-|U|$, since each odd component in $G-U$ needs a vertex in $U$. Hence
$$\nu(G) \leq \frac{|V|}{2}-\frac{o(G-U)-|U|}{2} \leq \frac{1}{2}(|V|+|U|-o(G-U))$$
Corollary 5 (Tutte’s 1-factor theorem) $G$ has a perfect matching iff $\forall U \subseteq V o(G-U) \leq|U|$.
The formula shows that the decision version of matching is in NP $\cap$ coNP . Edmonds gave the first polynomial time algorithms for finding a maximum cardinality matching and also more difficult maximum weight matching problem. As a consequence of his algorithmic work, Edmonds showed the following results on matching polytopes.
Consider the following polytope:
\begin{aligned} \sum_{e \in \delta(v)} x(e) & \leq 1 \quad \forall v \in V \ \sum_{e \in E[U]} x(e) & \leq\left\lfloor\frac{|U|}{2}\right\rfloor \quad \forall U,|U| \text { odd } \ 0 & \leq x(e) \quad \forall e \in E \end{aligned}
Edmonds showed that the vertices of the above polytope are exactly the characteristic vectors of the matchings of $G$. Observe that the polytope has an exponential number of constraints. One can ask whether this description of the matching polytope useful. Clearly if one takes the convex hull of the matchings of $G$, one obtains a polytope in $\mathbb{R}^E$; one can do this for any combinatorial optimization problem and in general one gets an exponential number of inequalities.

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Bipartite Matchings

$$\max \sum_{e \in E} x(e) \sum_{-G \delta(*)} x(e) \quad \leq 1 \quad \forall u \in V x(e) \geq 0 \quad \forall e \in E$$

## 数学代写|组合优化代写Combinatorial optimization代考|Tutte-Berge formula

$$\nu(G) \leq \frac{1}{2}(|V|+|U|-o(G-U)) \quad \forall U \subseteq V$$

$$\nu(G) \leq \frac{|V|}{2}-\frac{o(G-U)-|U|}{2} \leq \frac{1}{2}(|V|+|U|-o(G-U))$$

$$\sum_{e \in \delta(v)} x(e) \leq 1 \quad \forall v \in V \sum_{e \in E[U]} x(e) \quad \leq\left\lfloor\frac{|U|}{2}\right\rfloor \quad \forall U,|U| \text { odd } 0 \leq x(e) \quad \forall e \in E$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|COMP567

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Introduction and Motivation

Roughly speaking, an optimization problem has the following outline: given an instance of the problem, find the “best” solution among all solutions to the given instance. We will be mostly interested in discrete optimization problems where the instances and the solution set for each instance is from a discrete set. This is in contrast to continuous optimization where the input instance and the solution set for an instance can come from a continuous domain. Some of these distinctions are not as clear-cut as linear programming shows.

We assume familiarity with the computational complexity classes $\mathbf{P}, \mathbf{N P}$, coNP . In this class we are mainly interested in polynomial time solvable “combinatorial” optimization problems. Combinatorial optimization problems are a subset of discrete optimization problems although there is no formal definition for them. A typical problem in combinatorial optimization has a ground set $E$ of objects and solutions correspond to some subsets of $2^E$ (the power set of $E$ ) and a typical goal is to find either a maximum or minimum weight solution for some given weights on $E$. For example, in the spanning tree problem, the ground set $E$ is the set of edges of a graph $G=(V, E)$ and the solutions are subsets of $E$ that correspond to spanning trees in $G$.

We will be interested in NP optimization problems – NPO problems for short. Formally, a problem $Q$ is a subset of $\Sigma^$, where $\Sigma$ is a finite alphabet such as binary. Each string $I$ in $Q$ is an instance of $Q$. For a string $x$ we use $|x|$ to denote its length. We say that $Q$ is an NPO problem if the following hold: (i) for each $x \in \Sigma^$ there is a polynomial time algorithm that can check if $x \in Q$, i.e., if $x$ is a valid instance of $Q$
(ii) for each instance $I$ there is a set $\operatorname{sol}(I) \subset \Sigma^$ such that (a) $\forall s \in \operatorname{sol}(I),|s|=\operatorname{poly}(|I|)$ (b) there exists a poly-time algorithm that on input $I$, s correctly outputs whether $s \in s o l(I)$ or not (iii) there is a function val : $\Sigma^ \times \Sigma^* \rightarrow \mathbb{Z}$ s.t. $\operatorname{val}(I, s)$ assigns an integer to each instance $I$ and $s \in \operatorname{sol}(I)$ and moreover val can be computed by a poly-time algorithm.

Given an NPO problem, we say it is a minimization problem if the goal is to compute, given $I \in Q$, $\arg \min {s \in \operatorname{sol}(I)} \operatorname{val}(I, s)$. It is a maximization problem if the goal is to compute arg $\max {s \in \operatorname{sol}(I)} v a l(I, s)$. A natural decision problem associated with an NPO problem (say, maximization) is: given $I$ and integer $k$, is there $s \in \operatorname{sol}(I)$ s.t. $\operatorname{val}(s, I) \geq k$.

Many problems we encounter are NPO problems. Some of them can be solved in polynomial time. It is widely believed and conjectured that $\mathbf{P} \neq \mathbf{N P}$, which would mean that there are NPO problems (in particular, those whose decision versions are NP -complete) that do not have polynomial time algorithms. Assuming $\mathbf{P} \neq \mathbf{N P}$, some important and useful questions are: What problems are in $\mathbf{P}$ ? What characterizes problems in $\mathbf{P}$ ?

## 数学代写|组合优化代写Combinatorial optimization代考|Network Flow

Given directed graph $D=(V, A)$, two distinct nodes $s, t \in V$, and arc capacities $c: A \rightarrow \mathbb{R}^{+}$, a flow is a function $f: A \rightarrow \mathbb{R}^{+}$s.t.
(i) $\sum_{a \in \delta^{-}(v)} f(a)=\sum_{a \in \delta^{+}(v)} f(a)$ for all $v \in V-{s, t}$
(ii) $0 \leq f(a) \leq c(a)$ for all $a \in A$
The value of $f$ is
$$\operatorname{val}(f)=\sum_{a \in \delta^{+}(s)} f(a)-\sum_{a \in \delta^{-}(s)} f(a)=\sum_{a \in \delta^{-}(t)} f(a)-\sum_{a \in \delta^{+}(t)} f(a)$$
The optimization problem is to maximize the flow from $s$ to $t$.
An $s$ – $t$ cut is a partition of $V$ into $(A, B)$ s.t. $s \in A, t \in B$, and the capacity of this cut is
$$c(A, B)=\sum_{a \in \delta^{+}(A)} c(a)$$
Clearly, for any $s$ – $t$ flow $f$ and any $s$ – $t$ cut $(A, B)$
$$\operatorname{val}(f) \leq c(A, B) \Rightarrow \max s-t \text { flow } \leq \min s-t \text { cut capacity }$$
The well-known maxflow-mincut theorem of Menger and Ford-Fulkerson states that
Theorem 1 In any directed graph, the max s-t flow value is equal to the min s-t cut capacity.

Ford and Fulkerson proved the above theorem algorithmically. Although their augmenting path algorithm is not a polynomial-time algorithm, it can be made to run in polynomial time with very slight modifications (for example, the Edmonds-Karp modification to use the shortest augmenting path). Moreover, the algorithm shows that there is an integer valued maximum flow whenever the capacities are integer valued. Thus we have

Theorem 2 In any directed graph, the max s-t flow value is equal to the min s-t cut capacity. Moreover, if $c$ is integer valued then there is an integer valued maximum flow.

This is an example of a polynomial time (good) algorithm revealing structural properties of the problem in terms of a min-max result and integrality of flows. Conversely, suppose we knew the maxflow-mincut theorem but did not know any algorithmic result. Could we gain some insight? We claim that the answer is yes. Consider the decision problem: given $G, s, t$, is the $s$ – $t$ max flow value at least some given number $k$ ? It is easy to see that this problem is in NP since one can give a feasible flow $f$ of value at least $k$ as an NP certificate ${ }^1$. However, using the maxflow-mincut theorem we can also see that it is in coNP . To show that the flow value is smaller than $k$, all we need to exhibit is a cut of capacity smaller than $k$. Therefore the min-max result shows that the problem is in NP $\cap$ coNP . Most “natural” decision problems in NP $\cap$ coNP have eventually been shown to have polynomial time algorithms (there are a few well-known exceptions). Moreover, a problem in NP $\cap$ coNP being NP -complete or coNP -complete would imply that NP = coNP , some thing that most believe is unlikely. Thus a min-max result implies that the decision version is in NP $\cap$ coNP, strong evidence for the existence of a poly-time algorithm. That does not imply that such an algorithm will come by easily. Examples include matchings in general graphs and linear programming.

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Introduction and Motivation

(ii) 对于每个实例 $I$ 有一层 1 loperatorname{sol}(I) Isubset ISigma^ 这样 $(一) \forall s \in \operatorname{sol}(I),|s|=\operatorname{poly}(|I|)$
(b) 存在一个多时间算法，在输入 $I, \mathrm{~s}$ 正确输出是否 $s \in \operatorname{sol}(I)$ 或不 (iii) 有一个函数 val : $\Sigma^{\times} \Sigma^* \rightarrow \mathbb{Z}$ 英 石 $\operatorname{val}(I, s)$ 为每个实例分配一个整数 $I$ 和 $s \in \operatorname{sol}(I)$ 此外， val 可以通过多时间算法计算。

## 数学代写|组合优化代写Combinatorial optimization代考|Network Flow

\begin{aligned} & f: A \rightarrow \mathbb{R}^{+} \text {圣 } \ & \quad\left(\text { 一) } \sum_{a \in \delta^{-}(v)} f(a)=\sum_{a \in \delta^{+}(v)} f(a) \text { 对所有人 } v \in V-s, t\right. \ & \text { (二) } 0 \leq f(a) \leq c(a) \text { 对所有人 } a \in A \end{aligned}

$$\operatorname{val}(f)=\sum_{a \in \delta^{+}(s)} f(a)-\sum_{a \in \delta^{-}(s)} f(a)=\sum_{a \in \delta^{-}(t)} f(a)-\sum_{a \in \delta^{+}(t)} f(a)$$

$$c(A, B)=\sum_{a \in \delta^{+}(A)} c(a)$$

$$\operatorname{val}(f) \leq c(A, B) \Rightarrow \max s-t \text { flow } \leq \min s-t \text { cut capacity }$$
Menger 和 Ford-Fulkerson 著名的 maxflow-mincut 定理指出 定理 1 在任何有向图中，最大 st 流值等于最小 st 切割容量。
Ford 和 Fulkerson 通过算法证明了上述定理。尽管他们的增广路径算法不是多项式时间算法，但可以通过 非常轻微的修改使其在多项式时间内运行（例如，使用最短增广路径的 Edmonds-Karp 修改) 。此外，该 算法表明，只要容量为整数值，就有一个整数值的最大流量。因此我们有

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|APM6664

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|A4k(k + 1) Vertex Kernel

From the result in Sect. 4 we can devise a polynomial size kernel for CEVS. To achieve this we propose three reduction rules, prove that they are valid, and that their application gives a kernel as required.
Reduction Rule 1. Remove all isolated Cliques.
Lemma 10. Reduction Rule 1 is sound.
Proof. As no optimal solution has a final clique which bridges two connected components of a graph $G$ and an isolated clique needs no edits to make it complete, the clique will remain in all optimal solutions and as such can be removed without affecting the result.

Reduction Rule 2. Reduce all critical cliques with more than $k+1$ vertices to $k+1$ vertices.
Lemma 11. Reduction Rule 2 is sound.
Proof. As no solution clique in an optimal solution partially contains a critical clique and the cost to delete the edges incident to, or add edges to all of, or to divide the vertices of such a critical clique is greater than $k$ is too high to be allowed we only need to maintain this invariant. Thus we can remove vertices from any critical clique with more than $k+1$ vertices until there are at most $k+1$ vertices in a critical clique and this will not affect the result.

Reduction Rule 3. If there are mote than $4 k$ non-isolated critical cliques reduce the graph to a $P_3$ and set $k=0$ in this case.

## 数学代写|组合优化代写Combinatorial optimization代考|Our New Formulations

In $\left(P_2\right)$, for all $k \in \mathcal{K}$, variable $z^k$ is equal to 1 if and only if the optimal radius is greater than or equal to $D^k$. As a consequence, the following constraints are valid
$$z^k \geq z^{k+1} \quad k \in{1, \ldots, K-1} .$$
We first show that these inequalities are redundant for $\left(P_2\right)$. Let $\left(P_2^{\prime}\right)$ be the formulation obtained when constraints (4) are added to $\left(P_2\right)$ and let $v(\bar{F})$ be the optimal value of the linear relaxation of a given formulation $F$. We now prove that adding constraints (4) does not improve the quality of the linear relaxation.
Proposition 1. $v\left(\overline{P_2^{\prime}}\right)=v\left(\overline{P_2}\right)$
Proof. We show that an optimal solution $(\tilde{y}, \tilde{z})$ of the relaxation of $\left(P_2\right)$ satisfies (4). For each distance $D^k$ there exists a client $i(k)$ such that
$$\tilde{z}^k+\sum_{j: d_{i(k) j}<D^k} \tilde{y}_j=1$$
otherwise $\tilde{z}^k$ can be decreased and $(\tilde{y}, \tilde{z})$ is not optimal.

We now assume that $\tilde{z}^{k-1}<\tilde{z}^k$ for some index $k \in{2, \ldots, K}$. It follows that
$$\tilde{z}^{k-1}+\sum_{j: d_{i(k) j}<D^{k-1}} \tilde{y}j<\tilde{z}^k+\sum{j: d_{i(k) j}<D^k} \tilde{y}_j=1$$
The last equality follows from (5). Therefore, constraints (2c) for $i(k)$ and $k-1$ is violated.

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Our New Formulations

$$z^k \geq z^{k+1} \quad k \in 1, \ldots, K-1 .$$

$$\tilde{z}^k+\sum_{j: d_{i(k) j}<D^k} \tilde{y}j=1$$ 否则 $\tilde{z}^k$ 可以减少和 $(\tilde{y}, \tilde{z})$ 不是最优的。 我们现在假设 $\tilde{z}^{k-1}<\tilde{z}^k$ 对于某些索引 $k \in 2, \ldots, K$. 它遵循 $$\tilde{z}^{k-1}+\sum{j: d_{i(k) j}<D^{k-1}} \tilde{y} j<\tilde{z}^k+\sum j: d_{i(k) j}<D^k \tilde{y}_j=1$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|COMP567

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Edit Sequences in Add-Delete-Split Form

From the above lemmas we can deduce the following theorem.
Theorem 1. For every edit-sequence $S=e_1 \ldots e_k$ there is an edit-sequence $S^{\prime}=e_1^{\prime} \ldots e_{k^{\prime}}^{\prime}$ with equal or lesser length such that

1. if $e_i^{\prime}$ is an edge addition and $e_j^{\prime}$ is an edge deletion or a vertex splitting, then $i<j$
2. if $e_i^{\prime}$ is an edge deletion and $e_j^{\prime}$ is a vertex splitting, then $i<j$, and
3. $S^{\prime}$ contains no do-nothing operations.
We refer to an edit-sequence satisfying the statement of Theorem 1 as an edit-sequence in the add-delete-split form. We will now consider only these editsequences, as for any equivalence class of edit-sequences, there is a minimal member of that equivalence class which is in add-delete-split form. In fact, the equivalence class of an add-delete-split edit-sequence is the intersection of an equivalence class of edit-sequences and the set of edit-sequences in add-deletesplit form. A minimal member of any such equivalence class is an edit-sequence in add-delete-split form.

Uniqueness of the Pre-splitting Edge Modification Graph Corresponding to Any Add-Delete-Split Edit-Sequence Equivalence Class. It is now necessary to prove that in any equivalence class the graph obtained after the addition and deletion of edges and before splitting vertices is fixed. By doing so we provide a significant amount of structure to the problem, and do away with the direct use of edit-sequences altogether when searching for a solution.
The approach we adopt is to work on time-reversed edit-sequences, taking the final graph of the edit-sequence and the relation between the vertices in the initial graph and the final graph, and proving that we always arrive at the same graph.

## 数学代写|组合优化代写Combinatorial optimization代考|Critical Cliques

Originally introduced by Lin et al. [21], critical cliques provide a useful tool in understanding the clusters in graphs. A critical clique of a graph $G=(V, E)$ is a maximal induced subgraph $C$ of $G$ such that:
$-C$ is a complete graph.

• There is some subset $U \subseteq V$ such that for every $v \in V(C), N[v]=U$.
It was shown in [21] that each vertex is in exactly one critical clique. Let the critical clique containing a vertex $v$ be denoted by $C C(v)$. The critical clique graph $C C(G)$ can then also be defined as a graph with vertices being the critical cliques of $G$, having edges wherever there is an edge between the members of the critical cliques in the original graph [21]. That is to say, that the critical clique graph $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ related to the graph $G=(V, E)$ is the graph with $V^{\prime}-C C(G)$ and edges $E^{\prime}-\left{u v \mid \forall x \in V_C(u) \cdot \forall y \in V_C(v) \cdot x y \in E\right}$ Furthermore, the vertices in $G^{\prime}$ are given as a weight the number of vertices they represent in the original graph, similarly for the edges.

The following lemma, dubbed “the critical clique lemma” is adapted from Lemma 1 in [18], with a careful restatement in the context of this new problem.
Lemma 8. Any covering $C=\left(S_1 \ldots S_l\right)$ corresponding to a solution to CEVS for a graph $G=(V, E)$ that minimizes $k$ will always satisfy the following property: for any $v \in G$, and for any $S_i \in C$ either $C C(v) \subseteq S_i$ or $C C(v) \cap S_i=\emptyset$.
Proof omitted for length reasons.
By the critical clique lemma, the CEVS problem is equivalent to a weighted version of the problem on the critical clique graph.

Lemma 9. If there is a solution to CEVS on $(G, k)$ then there are at most $4 k$ non-isolated vertices in $C C(G)$. Moreover, there are at most $3 k+1$ vertices in any connected component of $C C(G)$ and there are at most $k$ connected components in $C C(G)$ which are non-isolated vertices.

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Edit Sequences in Add-Delete-Split Form

1. 如果和一世′是边加和和j′是边删除或顶点分裂，则一世<j
2. 如果和一世′是边删除和和j′是顶点分裂，那么一世<j， 和
3. 小号′不包含什么都不做的操作。
我们将满足定理 1 陈述的编辑序列称为增删分形式的编辑序列。我们现在将只考虑这些编辑序列，对于任何编辑序列的等价类，该等价类中有一个最小成员是添加-删除-拆分形式。实际上，增删分编辑序列的等价类是编辑序列等价类与增删分形式的编辑序列集合的交集。任何此类等价类的最小成员是添加-删除-拆分形式的编辑序列。

## 数学代写|组合优化代写Combinatorial optimization代考|Critical Cliques

$-C$ 是一个完整的图。

• 有一些子集 $U \subseteq V$ 这样对于每个 $v \in V(C), N[v]=U$.
在 [21] 中显示，每个顶点恰好在一个关键集团中。让包含顶点的临界集团 $v$ 表示为 $C C(v)$. 关键集团图 $C C(G)$ 然后也可以定义为一个图，其顶点是 $G$ ，在原始图中关键集团的成员之间有边的地方有边 [21]。 也就是说，临界集团图 $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$ 与图表有关 $G=(V, E)$ 是图表 $V^{\prime}-C C(G)$ 和边缘 权重给出它们在原始图中表示的顶点数，类似于边。
下面的引理，被称为“临界集团引理”，改编自 [18] 中的引理 1，并在这个新问题的背景下进行了仔细的重述。 引理 8. 任何覆盖 $C=\left(S_1 \ldots S_l\right)$ 对应于图的 CEVS 的解决方案 $G=(V, E)$ 最小化 $k$ 将始终满足以下属性: 对 于任何 $v \in G$ ，并且对于任何 $S_i \in C$ 任何一个 $C C(v) \subseteq S_i$ 或者 $C C(v) \cap S_i=\emptyset$.
由于篇幅原因省略了证明。
根据临界团引理，CEVS 问题等同于临界团图问题的加权版本。
引理 9. 如果有解决 CEVS 的方法 $(G, k)$ 那么至多有 $4 k$ 中的非孤立顶点 $C C(G)$. 此外，最多有 $3 k+1$ 的任何连 接组件中的顶点 $C C(G)$ 最多有 $k$ 中的连接组件 $C C(G)$ 这是非孤立的顶点。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 数学代写|组合优化代写Combinatorial optimization代考|MTH5107

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 数学代写|组合优化代写Combinatorial optimization代考|Preliminaries

We assume familiarity with basic graph theoretic terminology. All graphs in this work are simple, unweighted and undirected. The vertex and edge sets of a graph $G$ are denoted by $V(G)$ and $E(G)$ respectively. For a subset $V^{\prime}$ of $V(G)$, we denote by $G\left[V^{\prime}\right]$ the subgraph of $G$ that is induced by $V^{\prime}$.

A kernelization or kernel for a parameterized problem $P$ is a polynomial time function that maps an instance $(I, k)$ to an instance $\left(I^{\prime}, k^{\prime}\right)$ of $P$ such that:

• $(I, k)$ is a YES instance for $P$ if and only if $\left(I^{\prime}, k^{\prime}\right)$ is a YES instance;
• $\left|I^{\prime}\right|<f(k)$ for some computable function $f$;
$-k^{\prime}<g(k)$ for some computable function $g$.
A proper kernelization is a kernelization such that $g(k)<k[3]$. The function $f(k)$ is also called the size of the kernel. A problem has a kernel if and only if it is $F P T$ [12], however not every FPT problem has a kernel of polynomial size [5].
• A k-partition of a set $S$ is a collection of pairwise disjoint sets $S_1, S_2, \ldots S_k$ such that $S=\bigcup_{i=1}^k S_i$. A $k$-covering of a set $S$ is a collection of sets $S_1, S_2, \ldots S_k$ such that $S=\bigcup_{i=1}^k S_i$. A cluster graph is a graph in which the vertex set of each connected component induces a clique.
• Problem Definition. The Cluster Editing With Vertex Splitting Problem (henceforth CEVS) is defined as follows. Given a graph $G=(V, E)$ and an integer $k$, can a cluster graph $G^{\prime}$ be obtained from $G$ by a $k$-edit-sequence $e_1 \ldots e_k$ of the following operations:
• do nothing,
• add an edge to $E$,
• delete an edge from $E$, and
• an inclusive vertex split, that is for some $v \in V$ partition the vertices in $N(v)$ into two sets $U_1, U_2$ such that $U_1 \cup U_2=N(v)$, then remove $v$ from the graph and add two new vertices $v_1$ and $v_2$ with $N\left(v_1\right)=U_1$ and $N\left(v_2\right)=U_2$.
A vertex $v \in V(G)$ is said to correspond to a vertex $v^{\prime} \in V\left(G^{\prime}\right)$, constructed from $G$ by an edit-sequence $S$ if $v^{\prime}$ is a leaf on the division-tree $T$ for $v$ defined as follows:
(i) $v$ is the root of the tree, and
(ii) if an edit sequence operation splits a vertex $u$ which lies on the tree then the two vertices that result from the split are children of $u$.

## 数学代写|组合优化代写Combinatorial optimization代考|Restricted Re-ordering of the Edit-Sequence

Two edit sequences $S=e_1 \ldots e_k$ and $S^{\prime}=e_1^{\prime} \ldots e_k^{\prime}$ are said to be equivalent if:

• $G_S$ and $G_{S^{\prime}}$, the graphs obtained from $G$ by $S$ and $S^{\prime}$ respectively are isomorphic to each other with isomorphism $f: V\left(G_S\right) \rightarrow V\left(G_{S^{\prime}}\right)$, and
• if $u_S \in V\left(G_S\right)$ and $u_{S^{\prime}}=f\left(u_S\right)$ then the division tree which $u_S$ is contained in and the division tree which $u_{S^{\prime}}$ is contained in share a common root. In other words, $u_S$ and $u_{S^{\prime}}$ correspond to the same vertex of the original graph.
Lemma 1. For any edit-sequence $S=e_1 \ldots e_i e_{i+1} \ldots e_k$ where $e_i$ is an edge deletion and $e_{i+1}$ is an edge addition, there is an equivalent edit-sequence $S^{\prime}=$ $e_1 \ldots e_i^{\prime} e_{i+1}^{\prime} \ldots e_k$ of the same length where either $e_i^{\prime}$ is an edge addition and $e_{i+1}^{\prime}$ is an edge deletion, or both $e_i^{\prime}$ and $e_{i+1}^{\prime}$ are do-nothing operations.

Proof. We begin by noting that we only have to consider the edits $e_i$ and $e_{i+1}$ as we can think of the edit-sequence being a sequence of functions composed with each other, thus if $e_i$ deletes edge $u v$ and $e_{i+1}$ adds edge $w x$ then the graph immediately after applying the two operations in the opposite order will be the same in all cases except that where $u v=w x$ whereby the net effect is that nothing happens, as required.

Lemma 2. For any edit-sequence $S=e_1 \ldots e_i e_{i+1} \ldots e_k$ where $e_i$ is a vertex splitting and $e_{i+1}$ is an edge deletion there is an equivalent edit-sequence $S^{\prime}=$ $e_1 \ldots e_i^{\prime} e_{i+1}^{\prime} \ldots e_k$ where either $e_i^{\prime}$ is an edge deletion and $e_{i+1}$ is a vertex splitting or $e_i^{\prime}$ is a do-nothing operation and $e_{i+1}^{\prime}$ is a vertex splitting.

Proof. If the edge deleted by $e_{i+1}$ is not incident to one of the resulting vertices of the splitting $e_i$ then swapping the two operations produces the required editsequence $E^{\prime}$. Otherwise let $e_i$ split vertex $v$ and $e_{i+1}$ delete edge $u v_i$. Then if $e_i$ has associated covering $U_1, U_2$ of $N(v)$ and without loss of generality $u \in U_1$ then if $u \notin U_2$ then the edit-sequence with $e_i^{\prime}$ being a deletion operation deleting $u v$ and $e_i^{\prime}$ being the vertex splitting and $U_i^{\prime}=U_i \backslash{u}$ and $U_1^{\prime}=U_2$ is equivalent to $E$. Otherwise, $u \in U_1 \cap U_2$. Without loss of generality, suppose $u v_2$ is deleted by $e_{i+1}$. Then the sequence where $e_i^{\prime}$ is a do-nothing operation and where $e_{i+1}^{\prime}$ is a vertex splitting on $v$ with covering $U_1^{\prime}, U_2^{\prime}$ with $U_1^{\prime}=U_1$ and $U_2^{\prime}=U_2 \backslash{u}$ is equivalent.

# 组合优化代写

## 数学代写|组合优化代写Combinatorial optimization代考|Preliminaries

• $(I, k)$ 是一个YES 实例 $P$ 当且仅当 $\left(I^{\prime}, k^{\prime}\right)$ 是一个 YES 实例；
• $\left|I^{\prime}\right|<f(k)$ 对于一些可计算的函数 $f$; $-k^{\prime}<g(k)$ 对于一些可计算的函数 $g$.
适当的内核化是这样的内核化 $g(k)<k[3]$. 功能 $f(k)$ 也称为内核的大小。一个问题有一个内核当且仅当 它是 $F P T[12]$ ，但并非每个 FPT 问题都具有多项式大小的内核 [5]。
• 集合的 k-划分 $S$ 是成对不相交集的集合 $S_1, S_2, \ldots S_k$ 这样 $S=\bigcup_{i=1}^k S_i$.一个 $k$ – 集合的覆盖 $S$ 是集合的 集合 $S_1, S_2, \ldots S_k$ 这样 $S=\bigcup_{i=1}^k S_i$. 聚类图是其中每个连通分量的顶点集棌导团的图。
• 问题定义。顶点分裂问题的聚类编辑 (以下称为 CEVS) 定义如下。给定一个图 $G=(V, E)$ 和一个整数 $k$, 可以聚类图 $G^{\prime}$ 从获得 $G$ 通过一个 $k$-编辑序列 $e_1 \ldots e_k$ 以下操作:
• 没做什么，
• 添加一条边 $E$,
• 从中删除一条边 $E$, 和
• 包含顶点拆分，对于某些 $v \in V$ 划分顶点 $N(v)$ 分为两组 $U_1, U_2$ 这样 $U_1 \cup U_2=N(v)$, 然后删除 $v$ 从图 中添加两个新顶点 $v_1$ 和 $v_2$ 和 $N\left(v_1\right)=U_1$ 和 $N\left(v_2\right)=U_2$.
一个顶点 $v \in V(G)$ 据哾对应于一个顶点 $v^{\prime} \in V\left(G^{\prime}\right)$ ，由 $G$ 通过编辑序列 $S$ 如果 $v^{\prime}$ 是分裂树上的一片叶子 $T$ 为了 $v$ 定义如下:
(i) $v$ 是树的根，并且
(ii) 如果编辑序列操作拆分顶点 $u$ 它位于树上，那么分裂产生的两个顶点是 $u$.

## 数学代写|组合优化代写Combinatorial optimization代考|Restricted Re-ordering of the Edit-Sequence

• $G_S$ 和 $G_{S^{\prime}}$ ，从中获得的图表 $G$ 经过 $S$ 和 $S^{\prime}$ 分别同构同构 $f: V\left(G_S\right) \rightarrow V\left(G_{S^{\prime}}\right)$ ，和
• 如果 $u_S \in V\left(G_S\right)$ 和 $u_{S^{\prime}}=f\left(u_S\right)$ 然后划分树 $u_S$ 包含在和划分树中 $u_{S^{\prime}}$ 包含在共享一个公共根中。换句 话说， $u_S$ 和 $u_{S^{\prime}}$ 对应于原始图的相同顶点。
引理 1. 对于任何编辑序列 $S=e_1 \ldots e_i e_{i+1} \ldots e_k$ 在哪里 $e_i$ 是边删除和 $e_{i+1}$ 是边加法，有等价的编辑序 列 $S^{\prime}=e_1 \ldots e_i^{\prime} e_{i+1}^{\prime} \ldots e_k$ 相同长度的地方 $e_i^{\prime}$ 是边加和 $e_{i+1}^{\prime}$ 是边删除，或两者兼而有之 $e_i^{\prime}$ 和 $e_{i+1}^{\prime}$ 是什么 都不做的操作。
证明。我们首先注意到我们只需要考虑编辑 $e_i$ 和 $e_{i+1}$ 因为我们可以认为编辑序列是一系列相互组合的函数，因 此如果 $e_i$ 删除边 $u v$ 和 $e_{i+1}$ 增加优势 $w x$ 那么在以相反顺序应用两个操作之后的图形在所有情况下都是相同的，除 了 whereuv $=w x$ 因此，最终效果是没有任何事情发生，正如所要求的那样。
引理 2. 对于任何编辑序列 $S=e_1 \ldots e_i e_{i+1} \ldots e_k$ 在哪里 $e_i$ 是一个顶点分裂和 $e_{i+1}$ 是一个边缘删除有一个等 效的编辑序列 $S^{\prime}=e_1 \ldots e_i^{\prime} e_{i+1}^{\prime} \ldots e_k$ 哪里 $e_i^{\prime}$ 是边删除和 $e_{i+1}$ 是顶点分裂或 $e_i^{\prime}$ 是一个十么都不做的操作，并 且 $e_{i+1}^{\prime}$ 是顶点分裂。
证明。如果边被删除 $e_{i+1}$ 不附带于分裂的结果顶点之一 $e_i$ 然后交换这两个操作产生所需的编辑序列 $E^{\prime}$. 否则让 $e_i$ 分裂顶点 $v$ 和 $e_{i+1}$ 删除边 $u v_i$. 那么如果 $e_i$ 有相关的覆盖 $U_1, U_2$ 的 $N(v)$ 并且不失一般性 $u \in U_1$ 那么如果 $u \notin U_2$ 然后是编辑序列 $e_i^{\prime}$ 作为删除操作删除 $u v$ 和 $e_i^{\prime}$ 是顶点分裂和 $U_i^{\prime}=U_i \backslash u$ 和 $U_1^{\prime}=U_2$ 相当于 $E$. 否则， $u \in U_1 \cap U_2$. 不失一般性，假设 $u v_2$ 被删除 $e_{i+1}$. 然后顺序在哪里 $e_i^{\prime}$ 是一个什么也不做的操作，在哪里 $e_{i+1}^{\prime}$ 是 一个顶点分裂 $v$ 有覆盖物 $U_1^{\prime}, U_2^{\prime}$ 和 $U_1^{\prime}=U_1$ 和 $U_2^{\prime}=U_2 \backslash u$ 是等价的。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 计算机代写|组合优化代写Combinatorial optimization代考|MTH5107

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 计算机代写|组合优化代写Combinatorial optimization代考|Rectilinear Minimum Spanning Tree

Consider two points $A=\left(x_1, y_1\right)$ and $B=\left(x_2, y_2\right)$ in the plane. The rectilinear distance of $A$ and $B$ is defined by
$$d(A, B)=\left|x_1-x_2\right|+\left|y_1-y_2\right| .$$
The rectilinear plane is the plane with the rectilinear distance, denoted by $L_1$-plane. In this section, we study the following problem.

Problem 2.2.1 (Rectilinear Minimum Spanning Tree) Given $n$ points in the rectilinear plane, compute the minimum spanning tree on those $n$ given points.
In Chap. 1, we already present Kruskal algorithm which can compute a minimum spanning tree within $O(m \log n)$ time. In this section, we will improve this result by showing that the rectilinear minimum spanning tree can be computed in $O(n \log n)$ time. To do so, we first study an interesting problem as follows.

Problem 2.2.2 (All Northeast Nearest Neighbors) Consider a set $P$ of $n$ points in the rectilinear plane. For each $A=\left(x_A, y_A\right) \in P$, another point $B=\left(x_B, y_B\right) \in P$ is said to lie in northeast $(N E)$ area of $A$ if $x_A \leq x_B$ and $y_A \leq y_B$, but $A \neq B$. Furthermore, $B$ is the NE nearest neighbor of $A$ if $B$ has the shortest distance from A among all points lying in the $N E$ area of $A$. This problem is required to compute the NE nearest neighbor for every point in $P$. (The NE nearest neighbor of a point $A$ is “none” if no given point lies in the northeast area of $A$.)

Let us design a divide-and-conquer algorithm to solve this problem. For simplicity of description, assume all $n$ points have distinct $x$-coordinates and distinct $y$-coordinates. Now, we bisect $n$ points by a vertical line $L$. Let $P_l$ be the set of points lying on the left side of $L$ and $P_r$ the set of points lying on the right side of $L$. Suppose we already solve the all NE nearest neighbors problem on input point sets $P_l$ and $P_r$, respectively. Let us discuss how to combine solutions for two subproblems into a solution for all NE nearest neighbors on $P$.

For point $A$ in $P_r$, the NE nearest neighbor in $P_r$ is also the NE nearest neighbor in $P$. However, for point $A$ in $P_l$, the NE nearest neighbor in $P_l$ may not be the NE nearest neighbor in $P$. Actually, let $B_1$ denote the NE nearest neighbor of $A$ in $P_l$ and $B_r$ the NE nearest neighbor of $A$ for $B_2$ in $P_r$. Then, if $d\left(A, B_1\right) \leq d\left(A, B_2\right)$,then the NE nearest neighbor of $A$ in $P$ is $B_1$; otherwise, it is $B_2$. Therefore, to complete the combination task, it is sufficient to compute the NE nearest neighbors in $P_r$ for all points in $P_l$. We will show that this computation takes $O(n)$ time. To do so, let us first show a lemma.

## 计算机代写|组合优化代写Combinatorial optimization代考|Fibonacci Search

Consider a sequence of $n$ distinct integers which are stored in an array $A[1 \ldots n]$. An element $A[i]$ is a local maximum if $A[i-1]A[i+1]$ for $1S[i+1]$ for $i=1$, and $A[i-1]<A[i]$ for $i=n$. The sequence $A[1 . . n]$ is said to be bitonic if it contains exactly one local maximum, which is actually the global maximum one. Consider the following problem.

Problem 2.3.1 (Maximum Element in Bitonic Sequence) Given a sequence A[1..n of $n$ distinct integers, find the maximum element.
The problem can be solved by the following lemma.
Lemma 2.3.2 Assume $1 \leq iA[j]$, then $A[1 . . j-1]$ must contain a local maximum.
Proof First, assume $A[i]A[j+1]$. In this case, if none of $A[j], A[j-1], \ldots, A[i-1]$ is a local maximum, then $A[j]<A[j-1]<\cdots<A[i]$, contradicting to $A[i]<A[j]$.
Similarly, we can show the second statement. $n-j+1 \geq n / 3$. With such $i$ and $j$, for each comparison, the sequence can be cut off at least one third. Therefore, the maximum element can be found within $O(\log n)$ comparisons.

Next, we consider a situation that $A[i]=f(i)$, that is, $A[i]$ has to be obtained through evaluation of a function $f(i)$. Therefore, we want to find the maximum element with the minimum number of evaluations. In this situation, $i$ and $j$ will be selected based on a rule with Fibonacci number $F_i$ defined as follows:
$$F_0=F_1=1, F_i=F_{i-2}+F_{i-1} \text { for } i \geq 2 .$$
Associated Fibonacci search method is as follows.

## 计算机代写|组合优化代写Combinatorial optimization代考|Rectilinear Minimum Spanning Tree

$$d(A, B)=\left|x_1-x_2\right|+\left|y_1-y_2\right| .$$

## 计算机代写|组合优化代写Combinatorial optimization代考|Fibonacci Search

$$F_0=F_1=1, F_i=F_{i-2}+F_{i-1} \text { for } i \geq 2 .$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 计算机代写|组合优化代写Combinatorial optimization代考|COMP4743

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 计算机代写|组合优化代写Combinatorial optimization代考|Data Structure

A data structure is a data storage format which is organized and managed to have efficient access and modification. Each data structure has several standard operations. They are building bricks to construct algorithms. The data structure plays an important role in improving efficiency of algorithms. For example, we may introduce a data structure “Disjoint Sets” to improve Kruskal algorithm.

Consider a collection of disjoint sets. For each set $S$, let First $(S)$ denote the first node in set $S$. For each element $x$ in set $S$, denote First $(x)=\operatorname{First}(S)$. Define three operations as follows:
Make-Set $(x)$ creates a new set containing only $x$.
$\operatorname{Union}(x, y)$ unions sets $S_x$ and $S_y$ containing $x$ and $y$, respectively, into $S_x \cup S_y$, Moreover, set
$$\operatorname{First}\left(S_x \cup S_y\right)= \begin{cases}\operatorname{First}\left(S_x\right) & \text { if }\left|S_x\right| \geq\left|S_y\right|, \ \operatorname{First}\left(S_y\right) & \text { otherwise. }\end{cases}$$
Find-Set $(x)$ returns First $\left(S_x\right)$ where $S_x$ is the set containing element $x$.
With this data structure, Kruskal algorithm can be modified as follows.
Kruskal Algorithm
input: A connected graph $G=(V, E)$ with nonnegative edge weight $c: E \rightarrow R_{+}$.
output: A minimum spanning tree $T$.
Sort all edges $e_1, e_2, \ldots, e_m$ in nondecreasing order of weight,
An example for running this algorithm is as shown in Fig. 1.7.
Denote $m=|E|$ and $n=|V|$. Let us estimate the running time of Kruskal algorithm.

## 计算机代写|组合优化代写Combinatorial optimization代考|Algorithms with Self-Reducibility

There exist a large number of algorithms in which the problem is reduced to several subproblems, each of which is the same problem on a smaller-size input. Such a problem is said to have the self-reducibility, and the algorithm is said to be with self-reducibility.

For example, consider sorting problem again. Suppose input contains $n$ numbers. We may divide these $n$ numbers into two subproblems. One subproblem is the sorting problem on $\lfloor n / 2\rfloor$ numbers, and the other subproblem is the sorting problem on $\lceil n / 2\rceil$ numbers. After completely sorting each subproblem, combine two sorted sequences into one. This idea will result in a sorting algorithm, called the merge sort. The pseudocode of this algorithm is shown in Algorithm 1.

The main body calls a procedure. This procedure contains two self-calls, which means that the merge sort is a recursive algorithm, that is, the divide will continue until each subproblem has input of single number. Then this procedure employs another procedure (Merge) to combine solutions of subproblems with smaller inputs into subproblems with larger inputs. This computation process on input ${5,2,7,4,6,8,1,3}$ is shown in Fig. 2.1.

Note that the running time of procedure Merge at each level is $O(n)$. Let $t(n)$ be the running time of merge sort on input of size $n$. By the recursive structure, we can obtain that $t(1)=0$ and
$$t(n)=t(\lfloor n / 2\rfloor)+t(\lceil n / 2\rceil)+O(n) .$$
Suppose
$$t(n) \leq 2 \cdot t([n / 2\rceil)+c \cdot n$$
for some positive constant $c$. Define $T(1)=0$ and $$T(n)=2 \cdot T(\lceil n / 2\rceil)+c \cdot n .$$
By induction, we can prove that
$$t(n) \leq T(n) \text { for all } n \geq 1 .$$

## 计算机代写|组合优化代写Combinatorial optimization代考|Data Structure

Make-Set $(x)$ 创建一个新集合，仅包含 $x$.
$\operatorname{Union}(x, y)$ 工会集 $S_x$ 和 $S_y$ 包含 $x$ 和 $y$ ，分别为 $S_x \cup S_y$ ，此外，设置
$\operatorname{First}\left(S_x \cup S_y\right)=\left{\operatorname{First}\left(S_x\right) \quad\right.$ if $\left|S_x\right| \geq\left|S_y\right|, \operatorname{First}\left(S_y\right) \quad$ otherwise.

Kruskal 算法

## 计算机代写|组合优化代写Combinatorial optimization代考|Algorithms with Self-Reducibility

$$t(n)=t(\lfloor n / 2\rfloor)+t(\lceil n / 2\rceil)+O(n) .$$

$$t(n) \leq 2 \cdot t([n / 2\rceil)+c \cdot n$$

$$T(n)=2 \cdot T(\lceil n / 2\rceil)+c \cdot n .$$

$$t(n) \leq T(n) \text { for all } n \geq 1 .$$

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。

## 计算机代写|组合优化代写Combinatorial optimization代考|CAAM574002

statistics-lab™ 为您的留学生涯保驾护航 在代写组合优化Combinatorial optimization方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写组合优化Combinatorial optimization代写方面经验极为丰富，各种代写组合优化Combinatorial optimization相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 计算机代写|组合优化代写Combinatorial optimization代考|Optimal and Approximation Solutions

Let us show an optimality condition for the minimum spanning tree.
Theorem 1.2.1 (Path Optimality) A spanning tree $T^*$ is a minimum spanning tree if and only if it satisfies the following condition:

Path Optimality Condition For every edge $(u, v)$ not in $T^$, there exists a path $p$ in $T^$, connecting $u$ and $v$, and moreover, $c(u, v) \geq c(x, y)$ for every edge $(x, y)$ in path $p$.

Proof Suppose, for contradiction, that $c(u, v)<c(x, y)$ for some edge $(x, y)$ in the path $p$. Then $T^{\prime}=\left(T^* \backslash(x, y)\right) \cup(u, v)$ is a spanning tree with cost less than $c\left(T^\right)$, contradicting the minimaality of $T^$.

Conversely, suppose that $T^$ satisfies the path optimality condition. Let $T^{\prime}$ be a minimum spanning tree such that among all minimum spanning tree, $T^{\prime}$ is the one with the most edges in common with $T^$. Suppose, for contradiction, that $T^{\prime} \neq T^$. We claim that there exists an edge $(u, v) \in T^$ such that the path in $T^{\prime}$ between $u$ and $v$ contains an edge $(x, y)$ with length $c(x, y) \geq c(u, v)$. If this claim is true, then $\left(T^{\prime} \backslash(x, y)\right) \cup(u, v)$ is still a minimum spanning tree, contradicting the definition of $T^{\prime}$.

Now, we show the claim by contradiction. Suppose the claim is not true. Consider an edge $\left(u_1, v_1\right) \in T^* \backslash T^{\prime}$. the path in $T^{\prime}$ connecting $u_1$ and $v_1$ must contain an edge $\left(x_1, y_1\right)$ not in $T^$. Since the claim is not true, we have $c\left(u_1, v_1\right)$ connecting $x_1$ and $y_1$, which must contain an edge $\left(u_2, v_2\right) \notin$ $T^{\prime}$. Since $T^$ satisfies the path optimality condition, we have $c\left(x_1, y_1\right) \leq c\left(u_2, v_2\right)$. Hence, $c\left(u_1, v_1\right)$ such that $c\left(u_1, v_2\right)<c\left(u_2, v_2\right)<c\left(u_3, v_3\right)<\cdots$, contradicting the finiteness of $T^*$.

## 计算机代写|组合优化代写Combinatorial optimization代考|Running Time

The most important measure of quality for algorithms is the running time. However, for the same algorithm, it may take different times when we run it in different computers. To give a uniform standard, we have to get an agreement that runs algorithms in a theoretical computer model. This model is the multi-tape Turing machine which has been accepted by a very large population. Based on the Turing machine, the theory of computational complexity has been built up. We will touch this part of theory in Chap. 8 .

But, we will use RAM model to evaluate the running time for algorithms throughout this book except Chap. 8. In RAM model, assume that each line of pseudocode requires a constant time. For example, the running time of insertion sort is calculated in Fig. 1.6.

Actually, RAM model and Turing machine model are closely related. The running time estimated based on these two models is considered to be close enough. However, they are sometimes different in estimation of running time. For example, the following is a piece of pseudocode.
$$f(n) \leq c \cdot g(n) \text { for } n \geq n_0$$

There are two more notations which appear very often in representation of running time. $f(n)=\Omega 2(g(n))$ means that there exist constant $c>0$ and $n_0>0$ such that $0 \leq c \cdot g(n) \leq f(n)$ for $n \geq n_0$.
$f(n)=\Theta(g(n))$ means that there exist constants $c_1>0, c_2>0$ and $n_0>0$ such that
$$c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text { for } n \geq n_0 .$$
Finally, let us make a remark on input numbers.
In the minimum spanning tree problem, every edge has a nonnegative weight which is an input number. In the problem definition, we assumed that this is a real number. However, a real number cannot be exactly input in a computer. Actually, the computation of a real number is sometimes a very hard problem in the theory of computational complexity [260]. Therefore, we have to treat each real number with an oracle which can provide a rational number with expected accuracy, without computation cost. In other words, we ignore the computation trouble of the real number.

However, when our analysis of running time has to consider the size of input numbers, e.g., in analysis of weakly polynomial-time algorithms, we have to change the setting from the real number to the integer.

## 计算机代写|组合优化代写Combinatorial optimization代考|Optimal and Approximation Solutions

f(n) \leq c \cdot g(n) \text { for } n \geq n_0
$$还有另外两个符号经常出现在运行时间的表示中。 f(n)=\Omega 2(g(n)) 表示存在常数 c>0 和 n_0>0 这样 0 \leq c \cdot g(n) \leq f(n) 为了 n \geq n_0. f(n)=\Theta(g(n)) 表示存在常数 c_1>0, c_2>0 和 n_0>0 这样$$
c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text { for } n \geq n_0 .
J_{e^} \cap\left({\psi(v): v \in V(G)} \cup \bigcup_{f \in E(G) \backslash{e}} J_f\right)=\emptyset, $$\left|J_{e^} \cap J_e\right|-1, and if e^ is a loop then the face bounded by J_{e^} contains exactly one endpoint of e. Such an embedding is called a standard embedding of G^*. ## 组合优化代写 ## 数学代写|组合优化代写组合优化代考|欧拉和二部图 欧拉在Königsberg的七座桥的每座都恰好一次的问题上的工作是图论的起源。他通过定义一个图，要求一个包含所有边的walk，并观察到有两个以上的顶点具有奇数度，从而证明了这个问题是无法解决的 定义图G中的欧拉游动是一个包含所有边的闭合游动。无向图G如果每个顶点的度数是偶的，则称为欧拉图。如果每个v \in V(G)对应\left|\delta^{-}(v)\right|=\left|\delta^{+}(v)\right|，则有向图G是欧拉的 虽然欧拉既没有证明充分性，也没有明确考虑我们要求闭合行走的情况，但下面这个著名的结果通常被认为是他的 定理2.24。(Euler [1736]， Hierholzer[1873])连通(有向或无向)图具有欧拉行走当且仅当它是欧拉的 证明:度条件的必要性是显而易见的，因为在欧拉行走中出现k次的顶点(如果是第一个和最后一个顶点，则出现k+1次)必须有内度k和外度k，或者在无向情况下，度2 k 对于充分性，设W=v_1, e_1, v_2, \ldots, v_k, e_k, v_{k+1}是在G中走的最长的一段，即边数最多的一段。特别是，W必须包含所有离开v_{k+1}的边，这意味着度条件为v_{k+1}=v_1。所以W是关闭的。假设W不包含所有的边。当G被连接时，我们可以得出结论:有一个边e \in E(G)，它的e没有出现在W中，但至少有一个端点出现在W中，比如v_i。那么e就可以和v_i, e_i, v_{i+1}, \ldots, e_k, v_{k+1}=v_1, e_1, v_2, \ldots, e_{i-1}, v_i组合成一个比W还要长的步行。 ## 数学代写|组合优化代写组合优化代考|平面对偶性 我们现在要介绍一个重要的对偶概念。在本节中，图可能包含循环，即端点重合的边。在平面嵌入环路当然是用多边形而不是多边形弧来表示的 注意，欧拉公式(定理2.32)也适用于有环的图:这是根据观察得出的:将一个环e(即将e={v, v}替换为两条平行边{v, w},{w, v}，其中w是一个新顶点)和调整嵌入(将多边形J_e替换为两条多边形弧，其并集为J_e)增加了一个边和顶点的数量，但不改变面的数量 定义设G是一个有向或无向图，可能带有循环，设\Phi=\left(\psi,\left(J_e\right){e \in E(G)}\right)是G的平面嵌入。我们定义平面对偶G^，其顶点是\Phi的面，其边集是\left{e^: e \in E(G)\right}，其中e^连接与J_e相邻的面(如果J_e只与一个面相邻，则e^是一个循环)。在有向的情况下，例如对于e=(v, w)，我们将e^=\left(F_1, F_2\right)定位为这样一种方式，即当J_e从\psi(v)横贯到\psi(w)时，F_1是“向右”的面。G^也是平面的。事实上，显然存在一个平面嵌入G^的\left(\psi^,\left(J{e^}\right)_{e^* \in E\left(G^\right)}\right)，使得\psi^*(F) \in F对于\Phi的所有面都是F，对于每个面e \in E(G)，$$
J_{e^} \cap\left({\psi(v): v \in V(G)} \cup \bigcup_{f \in E(G) \backslash{e}} J_f\right)=\emptyset, $\left|J_{e^} \cap J_e\right|-1$，如果$e^$是一个循环，那么以$J_{e^}$为界的面只包含$e$的一个端点。这样的嵌入称为$G^*$的标准嵌入。

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。