亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We propose a new deterministic Kaczmarz algorithm for solving consistent linear systems $A\mathbf{x}=\mathbf{b}$. Basically, the algorithm replaces orthogonal projections with reflections in the original scheme of Stefan Kaczmarz. Building on this, we give a geometric description of solutions of linear systems. Suppose $A$ is $m\times n$, we show that the algorithm generates a series of points distributed with patterns on an $(n-1)$-sphere centered on a solution. These points lie evenly on $2m$ lower-dimensional spheres $\{\S_{k0},\S_{k1}\}_{k=1}^m$, with the property that for any $k$, the midpoint of the centers of $\S_{k0},\S_{k1}$ is exactly a solution of $A\mathbf{x}=\mathbf{b}$. With this discovery, we prove that taking the average of $O(\eta(A)\log(1/\varepsilon))$ points on any $\S_{k0}\cup\S_{k1}$ effectively approximates a solution up to relative error $\varepsilon$, where $\eta(A)$ characterizes the eigengap of the orthogonal matrix produced by the product of $m$ reflections generated by the rows of $A$. We also analyze the connection between $\eta(A)$ and $\kappa(A)$, the condition number of $A$. In the worst case $\eta(A)=O(\kappa^2(A)\log m)$, while for random matrices $\eta(A)=O(\kappa(A))$ on average. Finally, we prove that the algorithm indeed solves the linear system $A^T W^{-1}A \mathbf{x} = A^T W^{-1} \mathbf{b}$, where $W$ is the lower-triangular matrix such that $W+W^T = 2AA^T$. The connection between this linear system and the original one is studied. The numerical tests indicate that this new Kaczmarz algorithm has comparable performance to randomized (block) Kaczmarz algorithms.

Given a set $P$ of $n$ weighted points and a set $S$ of $m$ disks in the plane, the hitting set problem is to compute a subset $P'$ of points of $P$ such that each disk contains at least one point of $P'$ and the total weight of all points of $P'$ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line $\ell$. We present an $O((m+n)\log(m+n)+\kappa \log m)$ time algorithm for the problem, where $\kappa$ is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to $O((n + m)\log(m + n))$. In addition, we solve the problem in $O((m + n)\log(m + n))$ time in the $L_{\infty}$ and $L_1$ metrics, in which a disk is a square and a diamond, respectively. Our techniques can also be used to solve other geometric hitting set problems. For example, given in the plane a set $P$ of $n$ weighted points and a set $S$ of $n$ half-planes, we solve in $O(n^4\log n)$ time the problem of finding a minimum weight hitting set of $P$ for $S$. This improves the previous best algorithm of $O(n^6)$ time by nearly a quadratic factor.

Consider oriented graph nodes requiring periodic visits by a service agent. The agent moves among the nodes and receives a payoff for each completed service task, depending on the time elapsed since the previous visit to a node. We consider the problem of finding a suitable schedule for the agent to maximize its long-run average payoff per time unit. We show that the problem of constructing an $\varepsilon$-optimal schedule is PSPACE-hard for every fixed $\varepsilon \geq 0$, and that there exists an optimal periodic schedule of exponential length. We propose randomized finite-memory (RFM) schedules as a compact description of the agent's strategies and design an efficient algorithm for constructing RFM schedules. Furthermore, we construct deterministic periodic schedules by sampling from RFM schedules.

Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size $s\leq 2m\cdot\log(4m\Delta)$, where $m$ is the number of constraints, and $\Delta$ is the largest coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest $1$-norm $A_{\max}$ of any column of the constraint matrix, instead of $\Delta$. We show a support size upper bound of $s\leq m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$, by deriving a new bound on the -1 branch of the Lambert $\mathcal{W}$ function. Additionally, we provide a lower bound of $m\log(A_{\max})$, proving our result asymptotically optimal. Furthermore, we give support bounds of the form $s\leq 2m\cdot\log(1.46A_{\max})$. These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim., 2018), because all our upper bounds hold equally with $A_{\max}$ replaced by $\sqrt{m}\Delta$. Using our combinatorial result, we obtain the fastest known approximation schemes (EPTAS) for the fundamental scheduling problem of makespan minimization of uniformly related machines ($Q\mid\mid C_{\max}$).

We define a novel notion of ``non-backtracking'' matrix associated to any symmetric matrix, and we prove a ``Ihara-Bass'' type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with $k$ variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a $p$ fraction of assignments, if the instance contains $n$ variables and $n^{k/2} / \epsilon^2$ constraints, we can efficiently compute a certificate that the optimum satisfies at most a $p+O_k(\epsilon)$ fraction of constraints. Previously, this was known for even $k$, but for odd $k$ one needed $n^{k/2} (\log n)^{O(1)} / \epsilon^2$ random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck's inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is $o(n^{\lceil k/2 \rceil})$ and the third one cannot work when the number of constraints is $o(n^{k/2} \sqrt{\log n})$. We further apply our techniques to obtain a new PTAS finding assignments for $k$-CSP instances with $n^{k/2} / \epsilon^2$ constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.

We propose an algorithm whose input are parameters $k$ and $r$ and a hypergraph $H$ of rank at most $r$. The algorithm either returns a tree decomposition of $H$ of generalized hypertree width at most $4k$ or 'NO'. In the latter case, it is guaranteed that the hypertree width of $H$ is greater than $k$. Most importantly, the runtime of the algorithm is \emph{FPT} in $k$ and $r$. The approach extends to fractional hypertree width with a slightly worse approximation ($4k+1$ instead of $4k$). We hope that the results of this paper will give rise to a new research direction whose aim is design of FPT algorithms for computation and approximation of hypertree width parameters for restricted classes of hypergraphs.

The Kolmogorov-Arnold representation of a continuous multivariate function is a decomposition of the function into a structure of inner and outer functions of a single variable. It can be a convenient tool for tasks where it is required to obtain a predictive model that maps some vector input of a black box system into a scalar output. However, the construction of such representation based on the recorded input-output data is a challenging task. In the present paper, it is suggested to decompose the underlying functions of the representation into continuous basis functions and parameters. A novel lightweight algorithm for parameter identification is then proposed. The algorithm is based on the Newton-Kaczmarz method for solving non-linear systems of equations and is locally convergent. Numerical examples show that it is more robust with respect to the section of the initial guess for the parameters than the straightforward application of the Gauss-Newton method for parameter identification.

A set $S\subseteq V$ of vertices of a graph $G$ is a \emph{$c$-clustered set} if it induces a subgraph with components of order at most $c$ each, and $\alpha_c(G)$ denotes the size of a largest $c$-clustered set. For any graph $G$ on $n$ vertices and treewidth $k$, we show that $\alpha_c(G) \geq \frac{c}{c+k+1}n$, which improves a result of Wood [arXiv:2208.10074, August 2022], while we construct $n$-vertex graphs $G$ of treewidth~$k$ with $\alpha_c(G)\leq \frac{c}{c+k}n$. In the case $c\leq 2$ or $k=1$ we prove the better lower bound $\alpha_c(G) \geq \frac{c}{c+k}n$, which settles a conjecture of Chappell and Pelsmajer [Electron.\ J.\ Comb., 2013] and is best-possible. Finally, in the case $c=3$ and $k=2$, we show $\alpha_c(G) \geq \frac{5}{9}n$ and which is best-possible.

We establish convergence results related to the operator splitting scheme on the Cauchy problem for the nonlinear Schr\"odinger equation with rough initial data in $L^2$, $$ \left\{ \begin{array}{ll} i\partial_t u +\Delta u = \lambda |u|^{p} u, & (x,t) \in \mathbb{R}^d \times \mathbb{R}_+, u (x,0) =\phi (x), & x\in\mathbb{R}^d, \end{array} \right. $$ where $\lambda \in \{-1,1\}$ and $p >0$. While the Lie approximation $Z_L$ is known to converge to the solution $u$ when the initial datum $\phi$ is sufficiently smooth, the convergence result for rough initial data is open to question. In this paper, for rough initial data $\phi\in L^2 (\mathbb{R}^d)$, we prove the convergence of the Lie approximation $Z_L$ to the solution $u$ in the mass-subcritical range, $\max\left\{1,\frac{2}{d}\right\} \leq p < \frac{4}{d}$. Furthermore, our argument can be extended to the case of initial data $\phi\in H^s (\mathbb{R}^d)$ $(0<s\leq1)$, for which we obtain a convergence rate of order $\frac{s}{2-s}$ that breaks the natural order barrier $\frac{s}{2}$.

In a vertex-colored graph $G = (V, E)$, a subset $S \subseteq V$ is said to be consistent if every vertex has a nearest neighbor in $S$ with the same color. The problem of computing a minimum cardinality consistent subset of a graph is known to be NP-hard. On the positive side, Dey et al. (FCT 2021) show that this problem is solvable in polynomial time when input graphs are restricted to bi-colored trees. In this paper, we give a polynomial-time algorithm for this problem on $k$-colored trees with fixed $k$.