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

For several decades the dominant techniques for integer linear programming have been branching and cutting planes. Recently, several authors have developed core point methods for solving symmetric integer linear programs (ILPs). An integer point is called a core point if its orbit polytope is lattice-free. It has been shown that for symmetric ILPs, optimizing over the set of core points gives the same answer as considering the entire space. Existing core point techniques rely on the number of core points (or equivalence classes) being finite, which requires special symmetry groups. In this paper we develop some new methods for solving symmetric ILPs (based on outer approximations of core points) that do not depend on finiteness but are more efficient if the group has large disjoint cycles in its set of generators.

We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [RSW18]. This model arises as a natural special case of submodular function maximization: on query $S \subseteq V$, the oracle returns the total weight of the cut between $S$ and $V \backslash S$. For most constants $c \in (0,1]$, we nail down the query complexity of achieving a $c$-approximation, for both deterministic and randomized algorithms (up to logarithmic factors). Analogously to general submodular function maximization in the same model, we observe a phase transition at $c = 1/2$: we design a deterministic algorithm for global $c$-approximate max-cut in $O(\log n)$ queries for any $c < 1/2$, and show that any randomized algorithm requires $\tilde{\Omega}(n)$ queries to find a $c$-approximate max-cut for any $c > 1/2$. Additionally, we show that any deterministic algorithm requires $\Omega(n^2)$ queries to find an exact max-cut (enough to learn the entire graph), and develop a $\tilde{O}(n)$-query randomized $c$-approximation for any $c < 1$. Our approach provides two technical contributions that may be of independent interest. One is a query-efficient sparsifier for undirected weighted graphs (prior work of [RSW18] holds only for unweighted graphs). Another is an extension of the cut dimension to rule out approximation (prior work of [GPRW20] introducing the cut dimension only rules out exact solutions).

A matching $M$ in a graph $G$ is an \emph{acyclic matching} if the subgraph of $G$ induced by the endpoints of the edges of $M$ is a forest. Given a graph $G$ and a positive integer $\ell$, Acyclic Matching asks whether $G$ has an acyclic matching of size (i.e., the number of edges) at least $\ell$. In this paper, we first prove that assuming $\mathsf{W[1]\nsubseteq FPT}$, there does not exist any $\mathsf{FPT}$-approximation algorithm for Acyclic Matching that approximates it within a constant factor when the parameter is the size of the matching. Our reduction is general in the sense that it also asserts $\mathsf{FPT}$-inapproximability for Induced Matching and Uniquely Restricted Matching as well. We also consider three below-guarantee parameters for Acyclic Matching, viz. $\frac{n}{2}-\ell$, $\mathsf{MM(G)}-\ell$, and $\mathsf{IS(G)}-\ell$, where $n$ is the number of vertices in $G$, $\mathsf{MM(G)}$ is the matching number of $G$, and $\mathsf{IS(G)}$ is the independence number of $G$. Furthermore, we show that Acyclic Matching does not exhibit a polynomial kernel with respect to vertex cover number (or vertex deletion distance to clique) plus the size of the matching unless $\mathsf{NP}\subseteq\mathsf{coNP}\slash\mathsf{poly}$.

We study the Identity Problem, the problem of determining if a finitely generated semigroup of matrices contains the identity matrix; see Problem 3 (Chapter 10.3) in ``Unsolved Problems in Mathematical Systems and Control Theory'' by Blondel and Megretski (2004). This fundamental problem is known to be undecidable for $\mathbb{Z}^{4 \times 4}$ and decidable for $\mathbb{Z}^{2 \times 2}$. The Identity Problem has been recently shown to be in polynomial time by Dong for the Heisenberg group over complex numbers in any fixed dimension with the use of Lie algebra and the Baker-Campbell-Hausdorff formula. We develop alternative proof techniques for the problem making a step forward towards more general problems such as the Membership Problem. We extend our techniques to show that the fundamental problem of determining if a given set of Heisenberg matrices generates a group, can also be decided in polynomial time.

Motivated by the planarization of 2-layered straight-line drawings, we consider the problem of modifying a graph such that the resulting graph has pathwidth at most 1. The problem Pathwidth-One Vertex Explosion (POVE) asks whether such a graph can be obtained using at most $k$ vertex explosions, where a vertex explosion replaces a vertex $v$ by deg$(v)$ degree-1 vertices, each incident to exactly one edge that was originally incident to $v$. For POVE, we give an FPT algorithm with running time $O(4^k \cdot m)$ and an $O(k^2)$ kernel, thereby improving over the $O(k^6)$-kernel by Ahmed et al. [GD 22] in a more general setting. Similarly, a vertex split replaces a vertex $v$ by two distinct vertices $v_1$ and $v_2$ and distributes the edges originally incident to $v$ arbitrarily to $v_1$ and $v_2$. Analogously to POVE, we define the problem variant Pathwidth-One Vertex Splitting (POVS) that uses the split operation instead of vertex explosions. Here we obtain a linear kernel and an algorithm with running time $O((6k+12)^k \cdot m)$. This answers an open question by Ahmed et al. [GD22]. Finally, we consider the problem $\Pi$ Vertex Splitting ($\Pi$-VS), which generalizes the problem POVS and asks whether a given graph can be turned into a graph of a specific graph class $\Pi$ using at most $k$ vertex splits. For graph classes $\Pi$ that can be tested in monadic second-order graph logic (MSO$_2$), we show that the problem $\Pi$-VS can be expressed as an MSO$_2$ formula, resulting in an FPT algorithm for $\Pi$-VS parameterized by $k$ if $\Pi$ additionally has bounded treewidth. We obtain the same result for the problem variant using vertex explosions.

\textit{Pursuit-evasion games} have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. \textsc{Cops and Robber} (\CR) is one of the most well-known pursuit-evasion games played on graphs, where multiple \textit{cops} pursue a single \textit{robber}. The aim is to compute the \textit{cop number} of a graph, $k$, which is the minimum number of cops that ensures the \textit{capture} of the robber. From the viewpoint of parameterized complexity, \CR is W[2]-hard parameterized by $k$~[Fomin et al., TCS, 2010]. Thus, we study structural parameters of the input graph. We begin with the \textit{vertex cover number} ($\mathsf{vcn}$). First, we establish that $k \leq \frac{\mathsf{vcn}}{3}+1$. Second, we prove that \CR parameterized by $\mathsf{vcn}$ is \FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for \CR parameterized by $\mathsf{vcn}$ to admit a polynomial compression. We extend our exponential kernels to the parameters \textit{cluster vertex deletion number} and \textit{deletion to stars number}, and design a linear vertex kernel for \textit{neighborhood diversity}. Additionally, we extend all of our results to several well-studied variations of \CR.

We consider the classic 1-center problem: Given a set $P$ of $n$ points in a metric space find the point in $P$ that minimizes the maximum distance to the other points of $P$. We study the complexity of this problem in $d$-dimensional $\ell_p$-metrics and in edit and Ulam metrics over strings of length $d$. Our results for the 1-center problem may be classified based on $d$ as follows. $\bullet$ Small $d$: Assuming the hitting set conjecture (HSC), we show that when $d=\omega(\log n)$, no subquadratic algorithm can solve 1-center problem in any of the $\ell_p$-metrics, or in edit or Ulam metrics. $\bullet$ Large $d$: When $d=\Omega(n)$, we extend our conditional lower bound to rule out subquartic algorithms for 1-center problem in edit metric (assuming Quantified SETH). On the other hand, we give a $(1+\epsilon)$-approximation for 1-center in Ulam metric with running time $\tilde{O_{\varepsilon}}(nd+n^2\sqrt{d})$. We also strengthen some of the above lower bounds by allowing approximations or by reducing the dimension $d$, but only against a weaker class of algorithms which list all requisite solutions. Moreover, we extend one of our hardness results to rule out subquartic algorithms for the well-studied 1-median problem in the edit metric, where given a set of $n$ strings each of length $n$, the goal is to find a string in the set that minimizes the sum of the edit distances to the rest of the strings in the set.

The theory of mixed finite element methods for solving different types of elliptic partial differential equations in saddle-point formulation is well established since many decades. However, this topic was mostly studied for variational formulations defined upon the same finite-element product spaces of both shape- and test-pairs of primal variable-multiplier. Whenever these two product spaces are different the saddle point problem is asymmetric. It turns out that the conditions to be satisfied by the finite elements product spaces stipulated in the few works on this case may be of limited use in practice. The purpose of this paper is to provide an in-depth analysis of the well-posedness and the uniform stability of asymmetric approximate saddle point problems, based on the theory of continuous linear operators on Hilbert spaces. Our approach leads to necessary and sufficient conditions for such properties to hold, expressed in a readily exploitable form with fine constants. In particular standard interpolation theory suffices to estimate the error of a conforming method.

We propose a novel framework for analyzing the dynamics of distribution shift in real-world systems that captures the feedback loop between learning algorithms and the distributions on which they are deployed. Prior work largely models feedback-induced distribution shift as adversarial or via an overly simplistic distribution-shift structure. In contrast, we propose a coupled partial differential equation model that captures fine-grained changes in the distribution over time by accounting for complex dynamics that arise due to strategic responses to algorithmic decision-making, non-local endogenous population interactions, and other exogenous sources of distribution shift. We consider two common settings in machine learning: cooperative settings with information asymmetries, and competitive settings where a learner faces strategic users. For both of these settings, when the algorithm retrains via gradient descent, we prove asymptotic convergence of the retraining procedure to a steady-state, both in finite and in infinite dimensions, obtaining explicit rates in terms of the model parameters. To do so we derive new results on the convergence of coupled PDEs that extends what is known on multi-species systems. Empirically, we show that our approach captures well-documented forms of distribution shifts like polarization and disparate impacts that simpler models cannot capture.

Positive linear programs (LPs) model many graph and operations research problems. One can solve for a $(1+\epsilon)$-approximation for positive LPs, for any selected $\epsilon$, in polylogarithmic depth and near-linear work via variations of the multiplicative weight update (MWU) method. Despite extensive theoretical work on these algorithms through the decades, their empirical performance is not well understood. In this work, we implement and test an efficient parallel algorithm for solving positive LP relaxations, and apply it to graph problems such as densest subgraph, bipartite matching, vertex cover and dominating set. We accelerate the algorithm via a new step size search heuristic. Our implementation uses sparse linear algebra optimization techniques such as fusion of vector operations and use of sparse format. Furthermore, we devise an implicit representation for graph incidence constraints. We demonstrate the parallel scalability with the use of threading OpenMP and MPI on the Stampede2 supercomputer. We compare this implementation with exact libraries and specialized libraries for the above problems in order to evaluate MWU's practical standing for both accuracy and performance among other methods. Our results show this implementation is faster than general purpose LP solvers (IBM CPLEX, Gurobi) in all of our experiments, and in some instances, outperforms state-of-the-art specialized parallel graph algorithms.