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.     

An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions

The single facility location problem with demand regions seeks for a facility location minimizing the sum of the distances from n demand regions to the facility. The demand regions represent sales markets where the transportation costs are negligible. In this paper, we assume that all demand regions are disks of the same radius, and the distances are measured by a rectilinear norm, e.g. \(\ell _1\) or \(\ell _\infty \). We develop an exact combinatorial algorithm running in time \(O(n\log ^c n)\) for some c dependent only on the space dimension. The algorithm is generalizable to the other polyhedral norms.     

Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length

Given a weighted graph G on \(n + 1\) vertices, a spanning K-tree \(T_K\) of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree \(T_K\) whose \(n+K\) edges are assembled from some stock pieces of bounded length L. Let \(c_0\) be the sale price of each stock piece of length L and \(k(T_K)\) the number of minimum stock pieces to construct the \(n+K\) edges in \(T_K\). For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree \(T_K\), i.e., \(\min _{T_K}\{\sum _{e\in T_K} c(e)+ k(T_K)\cdot c_0\}\). The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A \(\frac{3}{2}\)-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.     

Algorithms for positive semidefinite factorization

This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an m-by-n nonnegative matrix X and an integer k, the PSD factorization problem consists in finding, if possible, symmetric k-by-k positive semidefinite matrices \(\{A^1,\ldots ,A^m\}\) and \(\{B^1,\ldots ,B^n\}\) such that \(X_{i,j}=\text {trace}(A^iB^j)\) for \(i=1,\ldots ,m\), and \(j=1,\ldots ,n\). PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size \(k=1+ \lceil \log _2(n) \rceil \) for the regular n-gons when \(n=5\), 8 and 10. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices \(A^i\) and \(B^j\) have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality \(A^i=B^i\) is required for all i).     

Robust optimization for routing problems on trees

The prize-collecting travelling salesman problem (pc-tsp) is a known variant of the classical travelling salesman problem. In the pc-tsp, we are given a weighted graph \(G=(V,E)\) with edge weights \(\ell :E\rightarrow {\mathbb {R}}_+\), a special vertex \(r\in V\), penalties \(\pi :V\rightarrow {\mathbb {R}}_+\) and the goal is to find a closed tour K such that \(r\in V(K)\) and such that the cost \(\ell (K)+\pi (V{\setminus } V(K))\), which is the sum of the weights of the edges in the tour and the cost of the vertices not spanned by K, is minimized. In this paper, we study the pc-tsp from a viewpoint of robust optimization. In our setting, an operator must find a closed tour in a (known) edge-weighted tree \(T=(V,E)\) starting and ending in the depot r while some of the edges may be blocked by “avalanches” defining the scenario \(\xi \). The cost \(f(K,\xi )\) of a tour K in scenario \(\xi \) is the cost resulting from “shortcutting” K, i.e. from restricting K to the nodes which are reachable from r in scenario \(\xi \), i.e. in the graph \(T {\setminus } \xi =(V,E{\setminus }\xi )\). In the absolute robust version of the problem one searches for a tour which minimizes the worst-case cost over all scenarios, while in the deviation robust counterpart, the regret, that is, the deviation from an optimum solution for a particular scenario, is sought to be minimized. We show that both versions of the problem can be solved in polynomial time on trees.     

The Terwilliger algebra of the incidence graph of the Hamming graph

Let \(\varGamma \) be a distance-semiregular graph on Y, and let \(D^Y\) be the diameter of \(\varGamma \) on Y. Let \(\varDelta \) be the halved graph of \(\varGamma \) on Y. Fix \(x \in Y\). Let T and \(T'\) be the Terwilliger algebras of \(\varGamma \) and \(\varDelta \) with respect to x, respectively. Assume, for an integer i with \(1 \le 2i \le D^Y\) and for \(y,z \in \varGamma _{2i}(x)\) with \(\partial _{\varGamma }(y,z)=2\), the numbers \(|\varGamma _{2i-1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) and \(|\varGamma _{2i+1}(x) \cap \varGamma (y) \cap \varGamma (z)|\) depend only on i and do not depend on the choice of y, z. The first goal in this paper is to show the relations between T-modules of \(\varGamma \) and \(T'\)-modules of \(\varDelta \). Assume \(\varGamma \) is the incidence graph of the Hamming graph H(D, n) on the vertex set Y and the set \({\mathcal {C}}\) of all maximal cliques. Then, \(\varGamma \) satisfies above assumption and \(\varDelta \) is isomorphic to H(D, n). The second goal is to determine the irreducible T-modules of \(\varGamma \). For each irreducible T-module W, we give a basis for W the action of the adjacency matrix on this basis and we calculate the multiplicity of W.     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Spectral density estimates with partial symmetries and an application to Bahri–Lions-type results

We are concerned with the existence of infinitely many solutions for the problem \(-\Delta u=|u|^{p-2}u+f\) in \(\Omega \), \(u=u_0\) on \(\partial \Omega \), where \(\Omega \) is a bounded domain in \(\mathbb {R}^N\), \(N\ge 3\). This can be seen as a perturbation of the problem with \(f=0\) and \(u_0=0\), which is odd in u. If \(\Omega \) is invariant with respect to a closed strict subgroup of O(N), then we prove infinite existence for all functions f and \(u_0\) in certain spaces of invariant functions for a larger range of exponents p than known before. In order to achieve this, we prove Lieb–Cwikel–Rosenbljum-type bounds for invariant potentials on \(\Omega \), employing improved Sobolev embeddings for spaces of invariant functions.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

On the estimates of the upper and lower bounds of Ramanujan primes

For \(n\ge 1\), the nth Ramanujan prime is defined as the least positive integer \(R_{n}\) such that for all \(x\ge R_{n}\), the interval \((\frac{x}{2}, x]\) has at least n primes. Let \(p_{i}\) be the ith prime and \(R_{n}=p_{s}\). Sondow, Laishram, and other scholars gave a series of upper bounds of s. In this paper we establish several results giving estimates of upper and lower bounds of Ramanujan primes. Using these estimates, we discuss a conjecture on Ramanujan primes of Sondow–Nicholson–Noe and prove that if \(n>10^{300}\), then \(\pi (R_{mn})\le m\pi (R_{n})\) for \(m\ge 1\).     

A generalization of sumset and its applications

Let A be a nonempty finite subset of an additive abelian group G and let r and h be positive integers. The generalized h-fold sumset of A, denoted by \(h^{(r)}A\), is the set of all sums of h elements of A, where each element appears in a sum at most r times. The direct problem for \(h^{(r)}A\) is to find a lower bound for \(|h^{(r)}A|\) in terms of |A|. The inverse problem for \(h^{(r)}A\) is to determine the structure of the finite set A for which \(|h^{(r)}A|\) is minimal with respect to some fixed value of |A|. If \(G = \mathbb {Z}\), the direct and inverse problems are well studied. In case of \(G = \mathbb {Z}/p\mathbb {Z}\), p a prime, the direct problem has been studied very recently by Monopoli (J. Number Theory, 157 (2015) 271–279). In this paper, we express the generalized sumset \(h^{(r)}A\) in terms of the regular and restricted sumsets. As an application of this result, we give a new proof of the theorem of Monopoli and as the second application, we present new proofs of direct and inverse theorems for the case \(G = \mathbb {Z}\).     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

The nestedness property of location problems on the line

We prove the existence of a nestedness property for a family of common convex parametric tactical serving facility location problems defined on the line. The parameter t is the length of the serving facility (closed interval). The nestedness property means that, given any two facility lengths \(t_1, t_2, 0 \le t_1<t_2\), there is an optimal solution with length \(t_1\) which lies within some optimal solution with length \(t_2\). The main idea of the proof is the representation of a serving facility as a point in \({\mathbb {R}}^2\) and the investigation of its geometrical properties. An intuitive graphical approach to the proof is given.     

Singular values of some modular functions

For an integer N greater than 5 and a triple \({\mathfrak{a}}=[a_{1},a_{2},a_{3}]\) of integers with the properties 0<a _i ≤N/2 and a _i ≠a _j for i≠j, we consider a modular function \(W_{\mathfrak{a}}(\tau)=\frac{\wp (a_{1}/N;L_{\tau})-\wp (a_{3}/N;L_{\tau})}{\wp (a_{2}/N;L_{\tau})-\wp(a_{3}/N;L_{\tau})}\) for the modular group Γ ₁(N), where ?(z;L _τ ) is the Weierstrass ?-function relative to the lattice L _τ generated by 1 and a complex number τ with positive imaginary part. For a pair of such triples \({\mathfrak{A}}=[{\mathfrak{a}},{\mathfrak{b}}]\) and a pair of non-negative integers F=[m,n], we define a modular function \(T_{{\mathfrak{A}},F}\) for the group Γ ₀(N) as the trace of the product \(W_{\mathfrak{a}}^{m}W_{\mathfrak{b}}^{n}\) to the modular function field of Γ ₀(N). In this article, we study the integrality of singular values of the functions \(W_{\mathfrak{a}}\) and \(T_{{\mathfrak{A}},F}\) by using their modular equations. We prove that the functions \(T_{{\mathfrak{A}},F}\) for suitably chosen \({\mathfrak{A}}\) and F generate the modular function field of Γ ₀(N), and from Shimura reciprocity and Gee–Stevenhagen method we obtain that singular values \(T_{{\mathfrak{A}},F}(\tau)\) for suitably chosen \({\mathfrak{A}}\) and F generate ring class fields. Further, we study the class polynomial of \(T_{{\mathfrak{A}},F}\) for Schertz N-system.     

Semidefinite bounds for nonbinary codes based on quadruples

For nonnegative integers q, n, d, let \(A_q(n,d)\) denote the maximum cardinality of a code of length n over an alphabet [q] with q letters and with minimum distance at least d. We consider the following upper bound on \(A_q(n,d)\). For any k, let \(\mathcal{C}_k\) be the collection of codes of cardinality at most k. Then \(A_q(n,d)\) is at most the maximum value of \(\sum _{v\in [q]^n}x(\{v\})\), where x is a function \(\mathcal{C}_4\rightarrow {\mathbb {R}}_+\) such that \(x(\emptyset )=1\) and \(x(C)=\!0\) if C has minimum distance less than d, and such that the \(\mathcal{C}_2\times \mathcal{C}_2\) matrix \((x(C\cup C'))_{C,C'\in \mathcal{C}_2}\) is positive semidefinite. By the symmetry of the problem, we can apply representation theory to reduce the problem to a semidefinite programming problem with order bounded by a polynomial in n. It yields the new upper bounds \(A_4(6,3)\le 176\), \(A_4(7,3)\le 596\), \(A_4(7,4)\le 155\), \(A_5(7,4)\le 489\), and \(A_5(7,5)\le 87\).     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

Structural Properties of Word Representable Graphs

Given a word \(w=w_1w_2\cdots w_n\) of length n over an ordered alphabet \(\Sigma _k\), we construct a graph \(G(w)=(V(w), E(w))\) such that V(w) has n vertices labeled \(1, 2,\ldots , n\) and for \(i, j \in V(w)\), \((i, j) \in E(w)\) if and only if \(w_iw_j\) is a scattered subword of w of the form \(a_{t}a_{t+1}\), \(a_t \in \Sigma _k\), for some \(1 \le t \le k-1\) with the ordering \(a_t<a_{t+1}\). A graph is said to be Parikh word representable if there exists a word w over \(\Sigma _k\) such that \(G=G(w)\). In this paper we characterize all Parikh word representable graphs over the binary alphabet in terms of chordal bipartite graphs. It is well known that the graph isomorphism (GI) problem for chordal bipartite graph is GI complete. The GI problem for a subclass of (6, 2) chordal bipartite graphs has been addressed. The notion of graph powers is a well studied topic in graph theory and its applications. We also investigate a bipartite analogue of graph powers of Parikh word representable graphs. In fact we show that for G(w), \(G(w)^{[3]}\) is a complete bipartite graph, for any word w over binary alphabet.     

Well-Quasi-Order of Relabel Functions

We define NLC\(_k^{\mathcal{F}}\) to be the restriction of the class of graphs NLC _k , where relabelling functions are exclusively taken from a set \(\mathcal{F}\) of functions from {1,...,k} into {1,...,k}. We characterize the sets of functions \(\mathcal{F}\) for which NLC\(_k^{\mathcal{F}}\) is well-quasi-ordered by the induced subgraph relation ≤? _i . Precisely, these sets \(\mathcal{F}\) are those which satisfy that for every \(f,g\in \mathcal{F}\), we have Im(f?°?g)?=?Im(f) or Im(g?°?f)?=?Im(g). To obtain this, we show that words (or trees) on \(\mathcal{F}\) are well-quasi-ordered by a relation slightly more constrained than the usual subword (or subtree) relation. A class of graphs is n-well-quasi-ordered if the collection of its vertex-labellings into n colors forms a well-quasi-order under ≤? _i , where ≤? _i respects labels. Pouzet (C R Acad Sci, Paris Sér A–B 274:1677–1680, 1972) conjectured that a 2-well-quasi-ordered class closed under induced subgraph is in fact n-well-quasi-ordered for every n. A possible approach would be to characterize the 2-well-quasi-ordered classes of graphs. In this respect, we conjecture that such a class is always included in some well-quasi-ordered NLC\(_k^{\mathcal{F}}\) for some family \(\mathcal{F}\). This would imply Pouzet’s conjecture.     

Conflict free colorings of nonuniform systems of infinite sets

If \(\mathcal{H}\) is a system of infinite sets, |A∩B|<r for \({A\ne B\in\mathcal{H}}\) (r<ω) then \(\mathcal{H}\) has a conflict free coloring with ω colors, i.e., a function \(F\colon {\bigcup\mathcal{H}\to\omega}\) so that each \(A\in\mathcal{H}\) has a color i<ω with |F ^?1(i)∩A|=1.     

Non-triviality conditions for integer-valued polynomial rings on algebras

Let D be a commutative domain with field of fractions K and let A be a torsion-free D-algebra such that \(A \cap K = D\). The ring of integer-valued polynomials on A with coefficients in K is \( Int _K(A) = \{f \in K[X] \mid f(A) \subseteq A\}\), which generalizes the classic ring \( Int (D) = \{f \in K[X] \mid f(D) \subseteq D\}\) of integer-valued polynomials on D. The condition on \(A \cap K\) implies that \(D[X] \subseteq Int _K(A) \subseteq Int (D)\), and we say that \( Int _K(A)\) is nontrivial if \( Int _K(A) \ne D[X]\). For any integral domain D, we prove that if A is finitely generated as a D-module, then \( Int _K(A)\) is nontrivial if and only if \( Int (D)\) is nontrivial. When A is not necessarily finitely generated but D is Dedekind, we provide necessary and sufficient conditions for \( Int _K(A)\) to be nontrivial. These conditions also allow us to prove that, for D Dedekind, the domain \( Int _K(A)\) has Krull dimension 2.