Search

Kovaleva and Spieksma (SIAM J Discrete Math 20(3):48–768, 2006) considered the problem of stabbing a given set of horizontal line segments with the smallest number of horizontal and vertical lines. The standard LP relaxation for this problem is easily shown to have an integrality gap of at most 2 by treating the horizontal and vertical lines separately. However, Kovaleva and Spieksma observed that threshold rounding can be used to obtain an integrality gap of e / (e - 1) ≈ 1.58 which is also shown to be tight. This is one of the rare known examples where the obvious upper bound of 2 on the integrality gap of the standard LP relaxation can be improved. Our goal in this paper is to extend their proof to two other problems where the goal is to stab a set R of objects with horizontal and vertical lines: in the first problem R is a set of horizontal and vertical line segments, and in the second problem R is a set of unit sized squares. The proof of Kovaleva and Spieksma essentially shows the existence of an appropriate threshold which yields the improved approximation factor. We begin by showing that a random threshold picked from an appropriate distribution works. This reduces the problem to finding an appropriate distribution for a desired approximation ratio. In the first problem, we show that the required distribution can be found by solving a linear program. In the second problem, while it seems harder to find the optimal distribution, we show that using the uniform distribution an improved approximation factor can still be obtained by solving a number of linear programs. [ABSTRACT FROM AUTHOR]

In this paper, we investigate representations of links that are either centrally symmetric in R3 or antipodally symmetric in S3. By using the notions of antipodally self-dual and antipodally symmetric maps, introduced and studied by the authors in [L. Montejano, J. L. Ramírez Alfonsín, and I. Rasskin, SIAM J. Discrete Math., 36 (2022), pp. 1551-1566], we are able to present sufficient combinatorial conditions for a link L to admit such representations. The latter naturally provide sufficient conditions for L to be amphichiral. We also introduce another (closely related) method yielding again sufficient conditions for L to be amphichiral. We finally prove that a link L, associated to a map G, is amphichiral if the self-dual pairing of G is not one of 6 specific cases among the classification of the 24 self-dual pairing Cor(G)⊳Aut(G). [ABSTRACT FROM AUTHOR]

In this paper, we adopt the augmented Lagrangian method (ALM) to solve convex quadratic second-order cone programming problems (SOCPs). Fruitful results on the efficiency of the ALM have been established in the literature. Recently, it has been shown in [Cui, Sun, and Toh, Math. Program., 178 (2019), pp. 381-415] that if the quadratic growth condition holds at an optimal solution for the dual problem, then the KKT residual converges to zero R-superlinearly when the ALM is applied to the primal problem. Moreover, Cui, Ding, and Zhao [SIAM J. 0ptim., 27 (2017), pp. 2332-2355] provided sufficient conditions for the quadratic growth condition to hold under the metric subregularity and bounded linear regularity conditions for solving composite matrix optimization problems involving spectral functions. Here, we adopt these recent ideas to analyze the convergence properties of the ALM when applied to SOCPs. To the best of our knowledge, no similar work has been done for SOCPs so far. In our paper, we first provide sufficient conditions to ensure the quadratic growth condition for SOCPs. With these elegant theoretical guarantees, we then design an SOCP solver and apply it to solve various classes of SOCPs, such as minimal enclosing ball problems, classical trust-region subproblems, square-root Lasso problems, and DIMACS Challenge problems. Numerical results show that the proposed ALM based solver is efficient and robust compared to the existing highly developed solvers, such as Mosek and SDPT3. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any pair of adjacent vertices have different sets consisting of colors assigned on their incident edges. The neighbor-distinguishing index of G , denoted by χ a ′ (G) , is the minimum number of colors in such an edge coloring of G . In this paper, we show that if G is a connected planar graph with maximum degree Δ ≥ 14 , then Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. This improves a result in [W. Wang, D. Huang, A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree, SIAM J. Discrete Math. 29(2015), 2412–2431], which says that every connected planar graph G with Δ ≥ 16 has Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. [ABSTRACT FROM AUTHOR]

In this paper we propose a method for computing the Faddeeva function w(z):... erfc(-iz) via truncated modified trapezoidal rule approximations to integrals on the real line. Our starting point is the method due to Matta and Reichel (Math. Comp. 25 (1971), pp. 339-344) and Hunter and Regan (Math. Comp. 26 (1972), pp. 339-541). Addressing shortcomings flagged by Weideman (SIAM. J. Numer. Anal. 31 (1994), pp. 1497-1518), we construct approximations which we prove are exponentially convergent as a function of N+1, the number of quadrature points, obtaining error bounds which show that accuracies of 2x10-15 in the computation of w(z) throughout the complex plane are achieved with N=11, this confirmed by computations. These approximations, moreover, provably achieve small relative errors throughout the upper complex half-plane where w(z) is non-zero. Numerical tests suggest that this new method is competitive, in accuracy and computation times, with existing methods for computing w(z) for complex z [ABSTRACT FROM AUTHOR]

In this paper, through an intuitive vanil la proximal method perspective, we derive a concise unified acceleration framework (UAF) for minimizing a convex function that has H\"older continuous derivatives with respect to general (non-Euclidean) norms. The UAF reconciles two different high-order acceleration approaches, one by Nesterov [Math. Program., 112 (2008), pp. 159-181] and one by Monteiro and Svaiter [SIAM J. Optim., 23 (2013), pp. 1092-1125]. As a result, the UAF unifies the high-order acceleration instances of the two approaches by only two problem-related parameters and two additional parameters for framework design. Meanwhile, the UAF (and its analysis) is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms. Furthermore, the UAF is the first approach that can match the existing lower bound of iteration complexity for minimizing a convex function with H\"older continuous derivatives. For practical implementation, we introduce a new and effective heuristic that significantly simplifies the binary search procedure required by the framework. We use experiments on logistic regression to verify the effectiveness of the heuristic. Finally, the UAF is proposed directly in the general composite convex setting and shows that the existing high-order algorithms can be naturally extended to the general composite convex setting. [ABSTRACT FROM AUTHOR]

For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau [SIAM J. Discrete Math., 29 (2015), pp. 65--78] and Perarnau and Reed [Combin. Probab. Comput., 26 (2017), pp. 448--467] studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots,s_r$ with each $s_{i + 1}$ sufficiently large relative to $s_i$, then with $1/\beta = \sum_{i = 2}^r \prod_{j = 1}^{i - 1} s_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, ${ex}(H,F)\ge \Delta^{-\beta - o(1)} \cdot e(H).$ This is tight as $\Delta \rightarrow \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that ${ex}(H,F)=O(\Delta^{-\beta}) \cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij [J. Lond. Math. Soc., 83 (2011), pp. 1091--1094] and Morris and Saxton [Adv. Math., 298 (2016), pp. 534--580]. General lower bounds for a wider class of $F$ are also obtained. [ABSTRACT FROM AUTHOR]

Litvak-Hinenzon et al. developed the phenomenological model to simulate the horizontal motion of particles in the atmosphere, and a series of their papers (see e.g., Litvak-Hinenzon et al. (Phys. D 164:213-250, 2002; Nonlinearity 15:1149-1177, 2002; SIAM J. Appl. Dyn. Syst. 3:525-573, 2004)) focused on studying the fate of parabolic resonance lower dimensional tori (as part of a quasi-periodic Hamiltonian pitchfork bifurcation (HPB) scenario in the unperturbed phenomenological model) under perturbations. However, the structural stability of quasi-periodic HPB involved therein has not been fully exposed theoretically (Litvak-Hinenzon et al. have only given some numerical explanations). Based on BCKV singularity theory established by Broer et al. (Z. Angew. Math. Phys. 44:389-432, 1993), we consider a more general quasi-periodic HPB triggered by the Z 2 -invariant universal unfolding N b c k v = a y 2 2 − (λ + b I 1) x 2 2 + c x 4 4 with respect to Z 2 -equivariant BCKV-restricted morphisms of the planar singularity a 2 y 2 + c 4 x 4 (the coefficients a , b , c ≠ 0 , the I 1 is regarded as distinguished parameter with respect to the external parameter λ). We prove a KAM (Kolmogorov–Arnold–Moser) theorem concerning parabolic tori in such quasi-periodic HPB, by which Diophantine parabolic tori (and the whole corresponding Diophantine HPB scenario) survive non-integrable and Z 2 -invariant Hamiltonian perturbations, parametrized by pertinent large Cantor sets. In the context of Z 2 -symmetry, our results can be seen as rigorous proof of the structural stability problem of bifurcations of Floquet-tori triggered by the universal unfolding N b c k v with distinguished parameters which is proposed by Broer et al. (Z. Angew. Math. Phys. 44:389-432, 1993). Ultimately, we similarly obtain the structural stability result of quasi-periodic HPB in the phenomenological model mentioned above, which can be utilized as a starting point for a deeper understanding of the various resonances and chaotic dynamics (in the gaps of the Cantor sets), just as Litvak-Hinenzon et al. did for normally parabolic tori undergoing a HPB. • We prove a KAM theorem in a quasi-periodic Hamiltonian pitchfork bifurcation. • We obtain the structural stability of a bifurcation in a phenomenological model. • We verify some of the previous numerical phenomena of Litvak-Hinenzon et al. [ABSTRACT FROM AUTHOR]