On the monotonicity of a data stream

In this paper we consider problems related to the sortedness of a data stream. In the first part of this work, we investigate the problem of estimating the distance to monotonicity; given a finite stream of length n from alphabet {1,...,m}, we give a deterministic (2+?)-approximation algorithm for estimating its distance to monotonicity in space \(O\left( {\tfrac{1} {{\varepsilon ^2 }}\log ^2 (\varepsilon n)} \right)\). This improves over the previous randomized (4+?)-approximation algorithm due to Gopalan, Jayram, Krauthgamer and Kumar in SODA 2007.     

A primal-dual large-update interior-point algorithm for <Emphasis Type="Italic">P</Emphasis><Subscript>*</Subscript>(<Emphasis Type="Italic">κ</Emphasis>)-LCP based on a new class of kernel functions

In this paper, we propose a large-update primal-dual interior point algorithm for P_*(κ)-linear complementarity problem. The method is based on a new class of kernel functions which is neither classical logarithmic function nor self-regular functions. It is determines both search directions and the proximity measure between the iterate and the center path. We show that if a strictly feasible starting point is available, then the new algorithm has \(o\left( {(1 + 2k)p\sqrt n {{\left( {\frac{1}{p}\log n + 1} \right)}^2}\log \frac{n}{\varepsilon }} \right)\)iteration complexity which becomes \(o\left( {(1 + 2k)\sqrt n log{\kern 1pt} {\kern 1pt} n\log \frac{n}{\varepsilon }} \right)\)with special choice of the parameter p. It is matches the currently best known iteration bound for P_*(κ)-linear complementarity problem. Some computational results have been provided.     

Computing Teichmüller Maps Between Polygons

By the Riemann mapping theorem, one can bijectively map the interior of an n-gon P to that of another n-gon Q conformally (i.e., in an angle-preserving manner). However, when this map is extended to the boundary, it need not necessarily map the vertices of P to those of Q. For many applications, it is important to find the “best” vertex-preserving mapping between two polygons, i.e., one that minimizes the maximum angle distortion (the so-called dilatation). Such maps exist, are unique, and are known as extremal quasiconformal maps or Teichmüller maps. There are many efficient ways to approximate conformal maps, and the recent breakthrough result by Bishop computes a \((1+\varepsilon )\)-approximation of the Riemann map in linear time. However, only heuristics have been studied in the case of Teichmüller maps. This paper solves the problem of finding a finite-time procedure for approximating Teichmüller maps in the continuous setting. Our construction is via an iterative procedure that is proven to converge in \(O(\text {poly}(1/\varepsilon ))\) iterations to a map whose dilatation is at most \(\varepsilon \) more than that of the Teichmüller map, for any \(\varepsilon >0\). We reduce the problem of finding an approximation algorithm for computing Teichmüller maps to two basic subroutines, namely, computing discrete (1) compositions and (2) inverses of discretely represented quasiconformal maps. Assuming finite-time solvers for these subroutines, we provide an approximation algorithm with an additive error of at most \(\varepsilon \).     

A spectra comparison theorem and its applications

We give a sharp comparison between the spectra of two Riemannian manifolds (Y, g) and \((X,g_0)\) under the following assumptions: \((X,g_0)\) has bounded geometry, (Y, g) admits a continuous Gromov–Hausdorff \(\varepsilon \)-approximation onto \((X,g_0)\) of non zero absolute degree, and the volume of (Y, g) is almost smaller than the volume of \((X,g_0)\). These assumptions imply no restrictions on the local topology or geometry of (Y, g) in particular no curvature assumption is supposed or inferred.     

Fast approximation of matroid packing and covering

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If \(\mathcal {M}\) is a matroid over a set of elements S with independent set \(\mathcal {I}\), and \(m=|S|\), we suppose that we are given an oracle function that takes an independent set \(A\in \mathcal {I}\) and an element \(e\in S\) and determines if \(A\cup \{e\}\) is independent in time I(m). Also, given that the elements of A are represented in an ordered way \(A=\{A_1,\dots ,A_k\}\), we denote the time to check if \(A\cup \{e\}\notin \mathcal {I}\) and if so, to find the minimum \(i\in \{0,\dots ,k\}\) such that \(\{A_1,\dots ,A_i\}\cup \{e\}\notin \mathcal {I}\) by \(I^*(m)\). Then, we describe a new FPTAS that computes for any \(\varepsilon >0\) and for any matroid \(\mathcal {M}\) of rank r over a set S of m elements, in memory space O(m), the packing \(\varLambda ({\mathcal {M}})\) within \(1+\varepsilon \) in time \(O(mI^*(m)\log (m)\log (m/r)/\varepsilon ^2)\), and the covering \(\varUpsilon ({\mathcal {M}})\) in time \(O(r\varUpsilon ({\mathcal {M}})I(m)\log (m)\log (m/r)/\varepsilon ^2)\). This method outperforms in time complexity by a factor of \(\varOmega (m/r)\) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of \(\varOmega (m)\) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others.     

Libera and Hilbert matrix operator on logarithmically weighted Bergman,Bloch and Hardy-Bloch spaces

We show that if α > 1, then the logarithmically weighted Bergman space \(A_{{{\log }^\alpha }}^2\) is mapped by the Libera operator L into the space \(A_{{{\log }^{\alpha - 1}}}^2\), while if α > 2 and 0 < ε ≤ α?2, then the Hilbert matrix operator H maps \(A_{{{\log }^\alpha }}^2\) into \(A_{{{\log }^{\alpha - 2 - \varepsilon }}}^2\).We show that the Libera operator L maps the logarithmically weighted Bloch space \({B_{{{\log }^\alpha }}}\), α ∈ R, into itself, while H maps \({B_{{{\log }^\alpha }}}\) into \({B_{{{\log }^{\alpha + 1}}}}\).In Pavlovi?’s paper (2016) it is shown that L maps the logarithmically weighted Hardy-Bloch space \(B_{{{\log }^\alpha }}^1\), α > 0, into \(B_{{{\log }^{\alpha - 1}}}^1\). We show that this result is sharp. We also show that H maps \(B_{{{\log }^\alpha }}^1\), α > 0, into \(B_{{{\log }^{\alpha - 1}}}^1\) and that this result is sharp also.     

The “strange term” in the periodic homogenization for multivalued Leray–Lions operators in perforated domains

Using the periodic unfolding method of Cioranescu, Damlamian and Griso, we study the homogenization for equations of the form

$-{\rm div}\,\,d_\varepsilon=f,\,\,{\rm with}\,\,\left(\nabla u_{\varepsilon , \delta }(x),d_{\varepsilon , \delta }(x)\right) \in A_\varepsilon(x)$

in a perforated domain with holes of size \({\varepsilon \delta }\) periodically distributed in the domain, where \({A_\varepsilon }\) is a function whose values are maximal monotone graphs (on R ^N ). Two different unfolding operators are involved in such a geometric situation. Under appropriate growth and coercivity assumptions, if the corresponding two sequences of unfolded maximal monotone graphs converge in the graph sense to the maximal monotone graphs A(x, y) and A ₀(x, z) for almost every \({(x,y,z)\in \Omega \times Y \times {\rm {\bf R}}^N}\), as \({\varepsilon \to 0}\), then every cluster point (u ₀, d ₀) of the sequence \({(u_{\varepsilon , \delta }, d_{\varepsilon , \delta } )}\) for the weak topology in the naturally associated Sobolev space is a solution of the homogenized problem which is expressed in terms of u ₀ alone. This result applies to the case where \({A_{\varepsilon}(x)}\) is of the form \({B(x/\varepsilon)}\) where B(y) is periodic and continuous at y = 0, and, in particular, to the oscillating p-Laplacian.

     

When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem

The vertex k-center selection problem is a well known NP-Hard minimization problem that can not be solved in polynomial time within a \(\rho < 2\) approximation factor, unless \(P=NP\). Even though there are algorithms that achieve this 2-approximation bound, they perform poorly on most benchmarks compared to some heuristic algorithms. This seems to happen because the 2-approximation algorithms take, at every step, very conservative decisions in order to keep the approximation guarantee. In this paper we propose an algorithm that exploits the same structural properties of the problem that the 2-approximation algorithms use, but in a more relaxed manner. Instead of taking the decision that guarantees a 2-approximation, our algorithm takes the best decision near the one that guarantees the 2-approximation. This results in an algorithm with a worse approximation factor (a 3-approximation), but that outperforms all the previously known approximation algorithms on the most well known benchmarks for the problem, namely, the pmed instances from OR-Lib (Beasly in J Oper Res Soc 41(11):1069–1072, 1990) and some instances from TSP-Lib (Reinelt in ORSA J Comput 3:376–384, 1991). However, the \(O(n^4)\) running time of this algorithm becomes unpractical as the input grows. In order to improve its running time, we modified this algorithm obtaining a \(O(n^2 \log n)\) heuristic that outperforms not only all the previously known approximation algorithms, but all the polynomial heuristics proposed up to date.     

Construction of sign-changing solutions for a harmonic equation with subcritical exponent

In this paper, we study the harmonic equation involving subcritical exponent \((P_{\varepsilon })\): \( \Delta u = 0 \), in \(\mathbb {B}^n\) and \(\displaystyle \frac{\partial u}{\partial \nu } + \displaystyle \frac{n-2}{2}u = \displaystyle \frac{n-2}{2} K u^{\frac{n}{n-2}-\varepsilon }\) on \( \mathbb {S}^{n-1}\) where \(\mathbb {B}^n \) is the unit ball in \(\mathbb {R}^n\), \(n\ge 5\) with Euclidean metric \(g_0\), \(\partial \mathbb {B}^n = \mathbb {S}^{n-1}\) is its boundary, K is a function on \(\mathbb {S}^{n-1}\) and \(\varepsilon \) is a small positive parameter. We construct solutions of the subcritical equation \((P_{\varepsilon })\) which blow up at two different critical points of K. Furthermore, we construct solutions of \((P_{\varepsilon })\) which have two bubbles and blow up at the same critical point of K.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

On the maximum TSP with <Emphasis Type="Italic">γ</Emphasis>-parameterized triangle inequality

The maximum TSP with γ-parameterized triangle inequality is defined as follows. Given a complete graph G = (V, E, w) in which the edge weights satisfy w(uv) ≤ γ · (w(ux) + w(xv)) for all distinct nodes \({u,x,v \in V}\), find a tour with maximum weight that visits each node exactly once. Recently, Zhang et al. (Theor Comput Sci 411(26–28):2537–2541, 2010) proposed a \({\frac{\gamma+1}{3\gamma}}\)-approximation algorithm for \({\gamma\in\left[\frac{1}{2},1\right)}\). In this paper, we show that the approximation ratio of Kostochka and Serdyukov’s algorithm (Upravlyaemye Sistemy 26:55–59, 1985) is \({\frac{4\gamma+1}{6\gamma}}\), and the expected approximation ratio of Hassin and Rubinstein’s randomized algorithm (Inf Process Lett 81(5):247–251, 2002) is \({\frac{3\gamma+\frac{1}{2}}{4\gamma}-O\left(\frac{1}{\sqrt{n}}\right)}\), for \({\gamma\in\left[\frac{1}{2},+\infty\right)}\). These improve the result in Zhang et al. (Theor Comput Sci 411(26–28):2537–2541, 2010) and generalize the results in Hassin and Rubinstein and Kostochka and Serdyukov (Inf Process Lett 81(5):247–251, 2002; Upravlyaemye Sistemy 26:55–59, 1985).     

On positive-influence target-domination

Consider a graph \(G=(V,E)\) and a vertex subset \(A \subseteq V\). A vertex v is positive-influence dominated by A if either v is in A or at least half the number of neighbors of v belong to A. For a target vertex subset \(S \subseteq V\), a vertex subset A is a positive-influence target-dominating set for target set S if every vertex in S is positive-influence dominated by A. Given a graph G and a target vertex subset S, the positive-influence target-dominating set (PITD) problem is to find the minimum positive-influence dominating set for target S. In this paper, we show two results: (1) The PITD problem has a polynomial-time \((1 + \log \lceil \frac{3}{2} \Delta \rceil )\)-approximation in general graphs where \(\Delta \) is the maximum vertex-degree of the input graph. (2) For target set S with \(|S|=\Omega (|V|)\), the PITD problem has a polynomial-time O(1)-approximation in power-law graphs.     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

Degree sequences and edge connectivity

For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\), this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

On scenario aggregation to approximate robust combinatorial optimization problems

As most robust combinatorial min–max and min–max regret problems with discrete uncertainty sets are NP-hard, research in approximation algorithm and approximability bounds has been a fruitful area of recent work. A simple and well-known approximation algorithm is the midpoint method, where one takes the average over all scenarios, and solves a problem of nominal type. Despite its simplicity, this method still gives the best-known bound on a wide range of problems, such as robust shortest path or robust assignment problems. In this paper, we present a simple extension of the midpoint method based on scenario aggregation, which improves the current best K-approximation result to an \((\varepsilon K)\)-approximation for any desired \(\varepsilon > 0\). Our method can be applied to min–max as well as min–max regret problems.     

Limit theorems for counting variables based on records and extremes

Hsu and Robbins (Proc. Nat. Acad. Sci. USA 33, 25–31, 1947) introduced the concept of complete convergence as a complement to the Kolmogorov strong law, in that they proved that \( {\sum }_{n=1}^{\infty } P(|S_{n}|>n\varepsilon )<\infty \) provided the mean of the summands is zero and that the variance is finite. Later, Erd?s proved the necessity. Heyde (J. Appl. Probab. 12, 173–175, 1975) proved that, under the same conditions, \(\lim _{\varepsilon \searrow 0} \varepsilon ^{2}{\sum }_{n=1}^{\infty } P(| S_{n}| \geq n\varepsilon )=EX^{2}\), thereby opening an area of research which has been called precise asymptotics. Both results above have been extended and generalized in various directions. Some time ago, Kao proved a pointwise version of Heyde’s result, viz., for the counting process \(N(\varepsilon ) ={\sum }_{n=1}^{\infty }1\hspace *{-1.0mm}\text {{I}} \{|S_{n}|>n\varepsilon \}\), he showed that \(\lim _{\varepsilon \searrow 0} \varepsilon ^{2} N(\varepsilon )\overset {d}{\to } E\,X^{2}{\int }_{0}^{\infty } 1\hspace *{-1.0mm}\text {I}\{|W(u)|>u\}\,du\), where W(?) is the standard Wiener process. In this paper we prove analogs for extremes and records for i.i.d. random variables with a continuous distribution function.     

The permutation of integers with small least common multiple of two subsequent terms

Erd?s, Freud and Hegyvári [1] constructed a permutation a ₁,a ₂,… of positive integers with \([a_{i}, a_{i+1}]< i\exp \left\{c\sqrt{\log i}\log\log i\,\right\}\) for an absolute constant c>0 and all i≧3. In this note, we construct a permutation of all positive integers such that for any ε>0 there exists an i ₀ with \([a_{i}, a_{i+1}]\allowbreak < i\exp \left\{\left(2\sqrt{2}+\varepsilon\right) \sqrt{\log i\log\log i}\,\right\}\) for all i≧i ₀.     

Approximations for constructing tree-form structures using specific material with fixed length

Substituting for the ordinary objective to minimize the sum of lengths of all edges in some graph structure of a weighted graph, we propose a new problem of constructing certain tree-form structure in same graph, where all edges needed in such a tree-form structure are supposed to be cut from some pieces of a specific material with fixed length. More precisely, we study a new problem defined as follows: a weighted graph \(G=(V,E; w)\), a tree-form structure \(\mathcal{S}\) and some pieces of specific material with length L, where a length function \(w:E\rightarrow Q^+\), satisfying \(w(u,v) \le L\) for each edge uv in G, we are asked how to construct a required tree-form structure \(\mathcal{S}\) as a subgraph \(G'\) of G such that each edge needed in \(G'\) is constructed by a part of a piece of such a specific material, the new objective is to minimize the number of necessary pieces of such a specific material to construct all edges in \(G'\). For this new objective defined, we obtain three results: (1) We present a \(\frac{3}{2}\)-approximation algorithm to construct a spanning tree of G; (2) We design a \(\frac{3}{2}\)-approximation algorithm to construct a single-source shortest paths tree of G; (3) We provide a 4-approximation algorithms to construct a metric Steiner tree of G.     

Complexity and approximation of the connected set-cover problem

In this paper, we study the computational complexity and approximation complexity of the connected set-cover problem. We derive necessary and sufficient conditions for the connected set-cover problem to have a polynomial-time algorithm. We also present a sufficient condition for the existence of a (1 +? ln ??)-approximation. In addition, one such (1 +? ln ??)-approximation algorithm for this problem is proposed. Furthermore, it is proved that there is no polynomial-time ${O(\log^{2-\varepsilon} n)}$ -approximation for any ${\varepsilon\,{>}\,0}$ for the connected set-cover problem on general graphs, unless NP has an quasi-polynomial Las-Vegas algorithm.