Maximum coverage problem with group budget constraints

We study the maximum coverage problem with group budget constraints (MCG). The input consists of a ground set X, a collection \(\psi \) of subsets of X each of which is associated with a combinatorial structure such that for every set \(S_j\in \psi \), a cost \(c(S_j)\) can be calculated based on the combinatorial structure associated with \(S_j\), a partition \(G_1,G_2,\ldots ,G_l\) of \(\psi \), and budgets \(B_1,B_2,\ldots ,B_l\), and B. A solution to the problem consists of a subset H of \(\psi \) such that \(\sum _{S_j\in H} c(S_j) \le B\) and for each \(i \in {1,2,\ldots ,l}\), \(\sum _{S_j \in H\cap G_i}c(S_j)\le B_i\). The objective is to maximize \(|\bigcup _{S_j\in H}S_j|\). In our work we use a new and improved analysis of the greedy algorithm to prove that it is a \((\frac{\alpha }{3+2\alpha })\)-approximation algorithm, where \(\alpha \) is the approximation ratio of a given oracle which takes as an input a subset \(X^{new}\subseteq X\) and a group \(G_i\) and returns a set \(S_j\in G_i\) which approximates the optimal solution for \(\max _{D\in G_i}\frac{|D\cap X^{new}|}{c(D)}\). This analysis that is shown here to be tight for the greedy algorithm, improves by a factor larger than 2 the analysis of the best known approximation algorithm for MCG.     

An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant \(\alpha >0\) is given in advance. Each job \(J_{j}\) has a normal processing time \(p_j\). Two jobs \(J_i\) and \(J_j\) are compatible if \(\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}\). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of \(1+\beta _\alpha \), where \(\beta _\alpha \) is the positive root of the equation \((1+\alpha )x^{2}+\alpha x=1+\alpha \).     

The solution of a generalized secretary problem via analytic expressions

Given integers \(1\le k<n\), the Gusein-Zade version of a generalized secretary problem is to choose one of the k best of n candidates for a secretary, which are interviewing in random order. The stopping rule in the selection is based only on the relative ranks of the successive arrivals. It is known that the best policy can be described by a non-decreasing sequence \((s_1, \ldots , s_k)\) of integers with \(l\le s_l<n\) for every \(1\le l\le k\), and conversely, any such a sequence determines the general structure of the best policy. We found a finite analytic expression for the probability of success when using the optimal policy with a sequence \((s_1, \ldots , s_k)\). We also study the problem of the construction of the optimal sequence, i.e. a sequence which maximizes the corresponding probability of success. We discovered finite analytic expressions which enable to calculate the elements \(s_l\) of an optimal sequence one by one, from \(l=k\) to \(l=1\). Until now, such expressions were derived separately, and only for the values \(k\le 3\).     

On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.     

The longest commonly positioned increasing subsequences problem

Based on the well-known longest increasing subsequence problem and longest common increasing subsequence (LCIS) problem, we propose the longest commonly positioned increasing subsequences (LCPIS) problem. Let \(A=\langle a_1,a_2,\ldots ,a_n\rangle \) and \(B{=}\left\langle b_1,b_2,\ldots ,b_n\right\rangle \) be two input sequences. Let \({ Asub}=\left\langle a_{i_1},a_{i_2},\ldots ,a_{i_l}\right\rangle \) be a subsequence of A and \({ Bsub}=\left\langle b_{j_1},b_{j_2},\ldots ,b_{j_l}\right\rangle \) be a subsequence of B such that \(a_{i_k}\le a_{i_{k+1}}, b_{j_k}\le b_{j_{k+1}}(1\le k<l)\), and \(a_{i_k}\) and \(b_{j_k}\) (\(1\le k\le l\)) are commonly positioned (have the same index \(i_k=j_k\)) in A and B respectively but these two elements do not need to be equal. The LCPIS problem aims at finding a pair of subsequences Asub and \({ Bsub}\) as long as possible. When all the elements of the two input sequences are positive integers, this paper presents an algorithm with \(O(n\log n \log \log M)\) time to compute the LCPIS, where \(M={ min}\{{ max}_{1\le i\le n}a_i,{ max}_{1\le j\le n}b_j\}\). And we also show a dual relationship between the LCPIS problem and the LCIS problem.     

Online covering salesman problem

Given a graph \(G=(V,E,D,W)\), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex \(i\in D\) is either on the tour or within a predetermined distance L to an arbitrary vertex \(j\in W\) on the tour, where \(D\subset V\),\(W\subset V\). In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound \(\frac{1}{1 + (k + 2)L}k+1\) and a CoverTreeTraversal algorithm for online CSP which is proved to be \(k+\alpha \)-competitive, where \(\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho \), \(\gamma \) is the approximation ratio for Steiner tree problem and \(\rho \) is the maximal number of locations that a customer can be served. When \(\frac{L}{\texttt {OPT}}\rightarrow 0\), our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.     

On the complete width and edge clique cover problems

A complete graph is the graph in which every two vertices are adjacent. For a graph \(G=(V,E)\), the complete width of G is the minimum k such that there exist k independent sets \(\mathtt {N}_i\subseteq V\), \(1\le i\le k\), such that the graph \(G'\) obtained from G by adding some new edges between certain vertices inside the sets \(\mathtt {N}_i\), \(1\le i\le k\), is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on \(3K_2\)-free bipartite graphs and polynomially solvable on \(2K_2\)-free bipartite graphs and on \((2K_2,C_4)\)-free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on \(\overline{3K_2}\)-free co-bipartite graphs and polynomially solvable on \(C_4\)-free co-bipartite graphs and on \((2K_2, C_4)\)-free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most \(2^k\) vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most \(2^k\) vertices. Finally we determine all graphs of small complete width \(k\le 3\).     

Total coloring of planar graphs without adjacent short cycles

In the study of computer science, optimization, computation of Hessians matrix, graph coloring is an important tool. In this paper, we consider a classical coloring, total coloring. Let \(G=(V,E)\) be a graph. Total coloring is a coloring of \(V\cup {E}\) such that no two adjacent or incident elements (vertex/edge) receive the same color. Let G be a planar graph with \(\varDelta \ge 8\). We proved that if for every vertex \(v\in V\), there exists two integers \(i_v,j_v\in \{3,4,5,6,7\}\) such that v is not incident with adjacent \(i_v\)-cycles and \(j_v\)-cycles, then the total chromatic number of graph G is \(\varDelta +1\).     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Total completion time minimization in online hierarchical scheduling of unit-size jobs

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least \(1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}\), where \(x=\sqrt{2m+4}\). We then present a greedy algorithm with tight competitive ratio of \(1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}\). The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when \(m=2\), we propose an optimal online algorithm with competitive ratio of \(16\) \(/\) \(13\), which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., \(n\rightarrow \infty \).     

Constant factor approximation for the weighted partial degree bounded edge packing problem

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph \(G=(V,E)\) with capacity \(c_v\in {\mathbb {N}}\) on each vertex v. The objective is to find a feasible subgraph \(G'=(V,E')\) maximizing \(|E'|\), where \(G'\) is said to be feasible if for each \(e=\{u,v\}\in E'\), \(\deg _{G'}(u)\le c_u\) or \(\deg _{G'}(v)\le c_v\). In the weighted version of the problem, additionally each edge \(e\in E\) has a weight w(e) and we want to find a feasible subgraph \(G'=(V,E')\) maximizing \(\sum _{e\in E'} w(e)\). The problem is already NP-hard if \(c_v = 1\) for all \(v\in V\) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an \(O(\log n)\)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with \(c_v = 1, \; \forall v\in V\) and having degree at most 3.     

Algorithms for connected <Emphasis Type="Italic">p</Emphasis>-centdian problem on block graphs

We consider the facility location problem of locating a set \(X_p\) of p facilities (resources) on a network (or a graph) such that the subnetwork (or subgraph) induced by the selected set \(X_p\) is connected. Two problems on a block graph G are proposed: one problem is to minimizes the sum of its weighted distances from all vertices of G to \(X_p\), another problem is to minimize the maximum distance from each vertex that is not in \(X_p\) to \(X_p\) and, at the same time, to minimize the sum of its distances from all vertices of G to \(X_p\). We prove that the first problem is linearly solvable on block graphs with unit edge length. For the second problem, it is shown that the set of Pareto-optimal solutions of the two criteria has cardinality not greater than n, and can be obtained in \(O(n^2)\) time, where n is the number of vertices of the block graph G.     

A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

A graph G is \((d_1, d_2)\)-colorable if its vertices can be partitioned into subsets \(V_1\) and \(V_2\) such that in \(G[V_1]\) every vertex has degree at most \(d_1\) and in \(G[V_2]\) every vertex has degree at most \(d_2\). Let \(\mathcal {G}_5\) denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in \(\mathcal {G}_5\) is \((d_1, d_2)\)-colorable, where \((d_1, d_2)\in \{(2,6), (3,5),(4,4)\}\). We still do not know even if there is a finite positive d such that every graph in \(\mathcal {G}_5\) is (1, d)-colorable. In this paper, we prove that every graph in \(\mathcal {G}_5\) without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in \(\mathcal {G}_5\;(1, 7)\)-colorable?.     

A heuristic for the time constrained asymmetric linear sum assignment problem

The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an \(n \times m, m \ge n\) benefit matrix \(B = (b_{ij})\), matching each row to a different column so that the sum of entries at the row-column intersections is maximised. This paper describes the application of a new fast heuristic algorithm, Asymmetric Greedy Search, to the asymmetric version (\(n \ne m\)) of the linear sum assignment problem. Extensive computational experiments, using a range of model graphs demonstrate the effectiveness of the algorithm. The heuristic was also incorporated within an algorithm for the non-sequential protein structure matching problem where non-sequential alignment between two proteins, normally of different numbers of amino acids, needs to be maximised.     

Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case \(m=2\). But the problem is unaddressed for \(m\ge 3\). In this paper, we present a best possible online algorithm for the problem with \(m\ge 3\), where the algorithm has a competitive ratio of 1.3028 for \(3\le m\le 5\) and 1.3146 for \(m\ge 6\).     

Convex median and anti-median at prescribed distance

The status of a vertex v in a connected graph G is the sum of the distances between v and all the other vertices of G. The subgraph induced by the vertices of minimum (maximum) status in G is called median (anti-median) of G. Let \(H=(G_1,G_2,r)\) denote a graph with \(G_1\) as the median and \(G_2\) as the anti-median of H, \(d(G_1,G_2)=r\) and both \(G_1\) and \(G_2\) are convex subgraphs of H. It is known that \((G_1,G_2,r)\) exists for every \(G_1\), \(G_2\) with \(r \ge \left\lfloor diam(G_1)/2\right\rfloor +\left\lfloor diam(G_2)/2\right\rfloor +2\). In this paper we show the existence of \((G_1,G_2,r)\) for every \(G_1\), \(G_2\) and \(r \ge 1\). We also obtain a sharp upper bound for the maximum status difference in a graph G.     

Weak {2}-domination number of Cartesian products of cycles

For a graph \(G=(V, E)\), a weak \(\{2\}\)-dominating function \(f:V\rightarrow \{0,1,2\}\) has the property that \(\sum _{u\in N(v)}f(u)\ge 2\) for every vertex \(v\in V\) with \(f(v)= 0\), where N(v) is the set of neighbors of v in G. The weight of a weak \(\{2\}\)-dominating function f is the sum \(\sum _{v\in V}f(v)\) and the minimum weight of a weak \(\{2\}\)-dominating function is the weak \(\{2\}\)-domination number. In this paper, we introduce a discharging approach and provide a short proof for the lower bound of the weak \(\{2\}\)-domination number of \(C_n \Box C_5\), which was obtained by St?pień, et al. (Discrete Appl Math 170:113–116, 2014). Moreover, we obtain the weak \(\{2\}\)-domination numbers of \(C_n \Box C_3\) and \(C_n \Box C_4\).     

On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$

For \(S\subseteq G\), let \(\kappa (S)\) denote the maximum number r of edge-disjoint trees \(T_1, T_2, \ldots , T_r\) in G such that \(V(T_i)\cap V(T_j)=S\) for any \(i,j\in \{1,2,\ldots ,r\}\) and \(i\ne j\). For every \(2\le k\le n\), the k-connectivity of G, denoted by \(\kappa _k(G)\), is defined as \(\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}\). Clearly, \(\kappa _2(G)\) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with \(\kappa _{3}=2\). Denote by \(\mathcal {H}\) the set of minimally 2-connected graphs with \(\kappa _{3}=2\). Let \(\mathcal {B}\subseteq \mathcal {H}\) and every graph in \(\mathcal {B}\) is either \(K_{2,3}\) or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that \(H\in \mathcal {H}\) if and only if \(H\in \mathcal {B}\) or H can be constructed from one or some graphs \(H_{1},\ldots ,H_{k}\) in \(\mathcal {B}\) (\(k\ge 1\)) by applying some operations recursively.     

An improved parameterized algorithm for the <Emphasis Type="Italic">p</Emphasis>-cluster vertex deletion problem

In the p-Cluster Vertex Deletion problem, we are given a graph \(G=(V,E)\) and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let \(r=p/k\). In this paper, we design a branching algorithm with time complexity \(O(\alpha ^k+|V||E|)\), where \(\alpha \) depends on r and has a rough upper bound \(\min \{1.618^{1+r},2\}\). With a more precise analysis, we show that \(\alpha =1.28\cdot 3.57^{r}\) for \(r\le 0.219\); \(\alpha =(1-r)^{r-1}r^{-r}\) for \(0.219< r<1/2\); and \(\alpha =2\) for \(r\ge 1/2\), respectively. Our algorithm also works with the same time complexity for the variant that the number of clusters is at most p. Our result improves the previous best time complexity \(O^*(1.84^{p+k})\) and implies that for fixed p the problem can be solved as efficiently as Vertex Cover.