Combinatorial Optimization and Applications

We show that the eccentricities (and thus the centrality indices) of all vertices of a $$\delta $$ -hyperbolic graph $$G=(V,E)$$ can be computed in linear time with an additive one-sided error of at most $$c\delta $$ , i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimate $$\hat{e}(v)$$ of its eccentricity $$ecc_G(v)$$ such that $$ecc_G(v)\le \hat{e}(v)\le ecc_G(v)+ c\delta $$ for a small constant c. We prove that every $$\delta $$ -hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, $$ecc_G(v)\le ecc_T(v)\le ecc_G(v)+ c\delta $$ . We also show that the distance matrix of G with an additive one-sided error of at most $$c'\delta $$ can be computed in $$O(|V|^2\log ^2|V|)$$ time, where $$c'< c$$ is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity.

This paper presents an optimal $$\varTheta (n \log n)$$ algorithm for determining time-minimal rectilinear paths among n transient rectilinear obstacles. An obstacle is transient if it exists in the scene only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among transient rectilinear obstacles and a pair of points s, d, we determine a time-minimal, obstacle-avoiding path from s to d. The main challenge in solving this problem arises as the robot may be required to wait for an obstacle to disappear, before it can continue moving toward the destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also solve a query version of this problem. For this, we build a planar subdivision with respect to a fixed source point, so that minimum arrival time to any query point can be reported in $$O(\log n)$$ time, using point location for the query point in this subdivision.

We propose a polynomial delay and polynomial space algorithm for the enumeration of k-degenerate induced subgraphs in a given graph. A graph G is k-degenerate if each of its induced subgraphs has a vertex of degree at most k. The degeneracy is considered as an indicator of the sparseness of the graph. Real-world graphs such as road networks, social networks and internet networks often have small degeneracy. Compared to other kinds of graph classes, bounded degeneracy does not give many structural properties such as induced subgraph free, or minor free. From this, using bounded degeneracy to reduce the time complexity is often not trivial. In this paper, we investigate ways of handling the degeneracy and propose an efficient algorithm for the k-degenerate induced subgraph enumeration. The time complexity is $$\mathcal {O}\left( \min \left\{ \varDelta + kk', (k')^2\right\} \right) $$ time per solution with polynomial preprocessing time and the space complexity is linear in the input graph size, where $$\varDelta $$ and $$k'$$ are the maximum degree and the degeneracy of the input graph.

A tree t-spanner of a graph G is a spanning subtree T in which the distance between any two adjacent vertices of G is at most t. The smallest t for which G has a tree t-spanner is the tree stretch index. The problem of determining the tree stretch index has been studied by: establishing lower and upper bounds, based, for instance, on the girth value and on the minimum diameter spanning tree problem, respectively; and presenting some classes for which t is a tight value. Moreover, in 1995, the computational complexities of determining whether $$t = 2$$ or $$t \ge 4$$ were settled to be polynomially time solvable and NP-complete, respectively, while deciding if $$t = 3$$ still remains an open problem.With respect to the computational complexity aspect of this problem, we present an inconsistence on the sufficient condition of tree 2-spanner admissible graphs. Moreover, while dealing with operations in graphs, we provide optimum tree t-spanners for 2 cycle-power graphs and for prism graphs, which are obtained from 2 cycle-power graphs after removing a perfect matching. Specifically, the stretch indexes for both classes are far from their girth’s natural lower bounds, and surprisingly, the parameter does not change after such a matching removal. We also present efficient strategies to obtain optimum tree t-spanners considering threshold graphs, split graphs, and generalized octahedral graphs. With this last result in addition to vertices addition operations and the tree decomposition of a cograph, we are able to present the stretch index for cographs.

We introduce the combinatorial optimization problem Time Disjoint Walks. This problem takes as input a digraph $$G$$ with positive integer arc lengths, and $$k$$ pairs of vertices that each represent a trip demand from a source to a destination. The goal is to find a path and delay for each demand so that no two trips occupy the same vertex at the same time, and so that the sum of trip times is minimized. We show that even for DAGs with max degree $$\varDelta \le 3$$ , Time Disjoint Walks is APX-hard. We also present a natural approximation algorithm, and provide a tight analysis. In particular, we prove that it achieves an approximation ratio of $$\varTheta (k/\log k)$$ on bounded-degree DAGs, and $$\varTheta (k)$$ on DAGs and bounded-degree digraphs.

Computing the directed path-width of a digraph is NP-hard even for digraphs of maximum semi-degree 3. In this paper we consider a family of graph classes called sequence digraphs, such that for each of these classes the directed path-width can be computed in polynomial time. For this purpose we define the graph classes $$S_{k,\ell }$$ as the set of all digraphs $$G=(V,A)$$ which can be defined by k sequences with at most $$\ell $$ entries from V, such that $$(u,v) \in A$$ if and only if in one of the sequences u occurs before v. We characterize digraphs which can be defined by $$k=1$$ sequence by four forbidden subdigraphs and also as a subclass of semicomplete digraphs. Given a decomposition of a digraph G into k sequences, we show an algorithm which computes the directed path-width of G in time , where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. k for the directed path-width problem. As most known parameterized algorithms for directed path-width consider the standard parameter, our algorithm improves significantly the known results for a high amount of digraphs of large directed path-width.

Solutions to genome scaffolding problems can be represented as paths and cycles in a “solution graph”. However, when working with repetitions, such solution graphs may contain branchings and, thus, they may not be uniquely convertible into sequences. Having introduced various ways of extracting the unique parts of such solutions, we extend previously known NP-hardness results to the case that the solution graph is planar, bipartite, and subcubic, and show that there is no PTAS in this case.

Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant $$\lambda $$ amounts to the NP-hard problem of finding a partial subgraph with maximum number of edges and spectral radius bounded above by $$\lambda $$ . A software-defined network (SDN) capable of real-time topology reconfiguration can then use an algorithm for finding such subgraph to quickly remove spreading malware threats without deploying specific security countermeasures.In this paper, we propose a novel randomized approximation algorithm based on the relaxation and rounding framework that achieves a $$O(\log n)$$ approximation in the case of finding a subgraph with spectral radius bounded by $$\lambda \in (\log n, \lambda _1(G))$$ where $$\lambda _1(G)$$ is the spectral radius of the input graph and n its number of nodes. We combine this algorithm with a maximum matching algorithm to obtain a $$O(\log ^2 n)$$ approximation algorithm for all values of $$\lambda $$ . We also describe how the mathematical programming formulation we give has several advantages over previous approaches which attempted at finding a subgraph with minimum spectral radius given an edge removal budget.

In this paper we are interested in finding communities with bipartite structure. A bipartite community is a pair of disjoint vertex sets S, $$S'$$ such that the number of edges with one endpoint in S and the other endpoint in $$S'$$ is “significantly more than expected.” This additional structure is natural to some applications of community detection. In fact, using other terminology, they have already been used to study correlation networks, social networks, and two distinct biological networks.In 2012 two groups independently ((1) Lee, Oveis Gharan, and Trevisan and (2) Louis, Raghavendra, Tetali, and Vempala) used higher eigenvalues of the normalized Laplacian to find an approximate solution to the k-sparse-cuts problem. In 2015 Liu generalized spectral methods for finding k communities to find k bipartite communities. Our approach improves the bounds on bipartite conductance (measure of strength of a bipartite community) found by Liu and also implies improvements to the original spectral methods by Lee et al. and Louis et al. We also highlight experimental results found when applying our algorithm to three distinct real-world networks.

The paper investigates relationship between algebraic expressions and labeled graphs. We consider directed grid graphs having m rows and n columns. Our intent is to simplify the expressions of these graphs. With that end in view, we describe two methods which generate expressions for directed grid graphs. For both methods, lengths of the expressions grow polynomially with n while m is determined as a constant parameter. Besides, we apply these methods to a square grid graph in which the number of rows is equal to the number of columns. We prove that the lengths of the expressions derived by the methods depend exponentially and quasi-polynomially, respectively, on the size of the graph.

Let G be a graph where every vertex has a colour and has specified diversity constraints, that is, a minimum number of neighbours of every colour. Every vertex also has a max-degree constraint: an upper bound on the total number of neighbours. In the Min-Edit-Cost problem, we wish to transform G using edge additions and/or deletions into a graph $$G'$$ where every vertex satisfies all diversity as well as max-degree constraints. We show an $$O(n^5 \log n)$$ algorithm for the Min-Edit-Cost problem, and an $$O(n^3 \log n \log \log n)$$ algorithm for the bipartite case. Given a specified number of edge operations, the Max-Satisfied-Nodes problem is to find the maximum number of vertices whose diversity constraints can be satisfied while ensuring that all max-degree constraints are satisfied. We show that the Max-Satisfied-Nodes problem is W[1]-hard, in parameter $$r+ \ell $$ , where r is the number of edge operations and $$\ell $$ is the number of vertices to be satisfied. We also show that it is inapproximable to within a factor of $$n^{1/2-\epsilon }$$ . For certain relaxations of the max-degree constraints, we are able to show constant-factor approximation algorithms for the problem.

We reduce the problem of computing a rectilinear shortest path between two given points s and t in the given splinegonal domain $$\mathcal {S}$$ to the problem of computing a rectilinear shortest path between two points in the polygonal domain. Our reduction algorithm defines a polygonal domain $$\mathcal {P}$$ from $$\mathcal {S}$$ by identifying a coreset of points on the boundaries of splinegons in $$\mathcal {S}$$ . Further, it transforms a shortest path between s and t amid polygonal obstacles in $$\mathcal {P}$$ to a shortest path between s and t amid splinegonal obstacles in $$\mathcal {S}$$ . When $$\mathcal {S}$$ is comprised of h pairwise disjoint splinegons defined with a total of n vertices, excluding the time to compute a rectilinear shortest path amid polygons in $$\mathcal {P}$$ , our reduction algorithm takes $$O(n + h \lg {n} + (\lg {h})^{1+\epsilon })$$ time. Here, $$\epsilon $$ is a small positive constant (resulting from the triangulation of the free space using [2]). For the special case of $$\mathcal {S}$$ comprising concave-in splinegons, we have devised another reduction algorithm which does not rely on the structures used in the algorithm (Inkulu and Kapoor [14]) to compute a rectilinear shortest path in the polygonal domain. Further, we have characterized few of the properties of rectilinear shortest paths amid splinegons which could be of independent interest.

In this paper we study variants of well-known graph problems: vertex cover, connected vertex cover, dominating set, total dominating set, independent dominating set, spanning tree, connected minimum weighted spanning graph, matching and hamiltonian path. Given a graph $$G=(V,E)$$ , we add a partition $$\varPi _{V}$$ (resp. $$\varPi _{E}$$ ) of its vertices (resp. of its edges). Now, any solution S containing an element (vertex or edge) of a part of this partition must also contain all the others ones. In other words, elements can only be added set by set, instead of one by one as in the classical situation (corresponding to obligations that are singletons). A motivation is to give a general framework and to study the complexity of combinatorial problems coming from systems where elements are interdependent. We propose hardness and approximation results.

We study the problem of determining whether a given graph $$G=(V,E)$$ admits a matching M whose removal destroys all odd cycles of G (or equivalently whether $$G-M$$ is bipartite). This problem is equivalent to determine whether G admits a (2, 1)-coloring, which is a 2-coloring of V(G) in which each color class induces a graph of maximum degree at most 1. We determine a dichotomy related to the NP-completeness of such a decision problem, where it is NP-complete even for 3-colorable planar graphs of maximum degree 4, while it is linear-time solvable for graphs of maximum degree at most 3. In addition, we present polynomial-time algorithms for many graph classes including those in which every odd-cycle subgraph is a triangle, graphs having bounded dominating sets, and $$P_5$$ -free graphs. Additionally, we show that this problem is fixed-parameter tractable when parameterized by the clique-width, which implies that it is polynomial-time solvable for many interesting graph classes, such as distance-hereditary, outerplanar, and chordal graphs.

Consider mitigating the effects of denial of service or of malicious traffic in networks by deleting edges. Edge deletion reduces the DoS or the number of the malicious flows, but it also inadvertently removes some of the desired flows. To model this important problem, we formulate two problems: (1) remove all the undesirable flows while minimizing the damage to the desirable ones and (2) balance removing the undesirable flows and not removing too many of the desirable flows. We prove these problems are equivalent to important theoretical problems, thereby being important not only practically but also theoretically, and very hard to approximate in a general network. We employ reductions to nonetheless approximate the problem and also provide a greedy approximation. When the network is a tree, the problems are still MAX SNP-hard, but we provide a greedy-based 2l-approximation algorithm, where l is the longest desirable flow. We also provide an algorithm, approximating the first and the second problem within $$2 \sqrt{ 2\left| E \right| }$$ and $$2 \sqrt{2 (\left| E \right| + \left| \text {undesirable flows} \right| )}$$ , respectively, where E is the set of the edges of the network. We also provide a fixed-parameter tractable (FPT) algorithm. Finally, if the tree has a root such that every flow in the tree flows on the path from the root to a leaf, we solve the problem exactly using dynamic programming.

Recently, emergency evacuation management, which is a social work around the world, has been getting lots of attentions due to its importance and necessity. The primary task of emergency evacuation management is evacuation route planning. Considering the particularity of restrict space scenarios, it is more important to guarantee the security and promptness of evacuation routes than that in open space scenarios. In this paper, we introduce a new evacuation route planning problem in restricted spaces, namely Congestion-Avoidable Evacuation Route Network Planning (CA-ERNP) problem. Based on the minimum cost maximum flow (Min-Max Flow) problem, we propose a batch scheduling algorithm based on node-slitting transformation. In addition, we evaluate the average performance of the algorithms via simulation and the results indicate the proposed algorithm outperforms the existing alternatives in terms of efficiency and time cost.

Yao’s millionaire protocol enables Alice and Bob to know whether or not Bob is richer than Alice by using a public-key cryptosystem without revealing the actual amounts of their properties. In this paper, we present a simple and practical implementation of Yao’s millionaire protocol using a deck of playing cards; we straightforwardly implement the idea behind Yao’s millionaire protocol so that even non-experts can easily understand its correctness and secrecy. Our implementation is based partially on the previous card-based scheme proposed by Nakai, Tokushige, Misawa, Iwamoto, and Ohta; their scheme admits players’ private actions on a sequence of cards called Private Permutation (PP), implying that a malicious player could make an active attack (for example, he/she could exchange some of the cards stealthily when doing such a private action). In contrast, our implementation relies on a familiar shuffling operation called a random cut, and hence, it can be conducted completely publicly so as to avoid any active attack.

Clique, as the most compact cohesive component in a graph, has been employed to identify cohesive subgroups of entities and explore the sensitive information in the online social network, crowdsourcing network, and cyber physical network, etc. In this study, we focus on the defense of clique-based attack and target at reducing the risk of entities security/privacy issues in clique structure. Since the ultimate resolution for defending the clique-based attack and risk is wrecking the clique with minimum cost, we establish the problem of clique-destroying (CD) in the network from a fundamental algorithm aspect. Interestingly, we notice that the clique-destroying problem in the directed graph is still an unsolved problem, and complexity analysis also does not exist. Therefore, we propose an innovative formal clique-destroying problem and proof the NP-complete problem complexity with solid theoretical analysis, then present effective and efficient algorithms for both undirected and directed graph. Furthermore, we show how to extend our algorithm to data privacy protection applications with controllable parameter k, which could adjust the size of a clique we wish to destroy. By comparing our algorithm with the up-to-date anonymization approaches, the real data experiment demonstrates that our resolution could efficaciously defend the clique-based security and privacy attacks.

Network reliability is the probability that a network system can perform a desired operation, such as communication between facilities, against stochastic equipment failures. On analyzing network systems that are represented by undirected graphs, the all-terminal reliability (ATR) is commonly used as one of the network reliability. As a natural extension of the ATR for the directed version, the strongly connected reliability (SCR) is known. The SCR should be computed on various network systems, such as ad-hoc network, that demand the property called strongly connected. Unfortunately, computing the SCR is known to be #P-complete, and little studies challenge the computation of the exact or an approximate SCR on limited graph classes. In this study, we propose the first practically efficient algorithm to compute the exact SCR in general. The algorithm constructs a binary decision diagram (BDD) representing all the strongly connected spanning subgraphs (SCSSs) in a given directed graph. Subsequently, the algorithm computes the exact SCR by a dynamic programming on the BDD. To efficiently construct BDDs, we designed a new variant of the frontier based search (FBS). We conducted computational experiments to evaluate the proposed algorithm. The results demonstrated that the proposed algorithm succeeded in computing the SCR in real-world networks with a few hundred edges within a reasonable time, which was previously impossible.

In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem.

We propose a related machine scheduling problem in which the speeds of machines are variables and must satisfy a system of linear constraints, and the processing times of jobs are given and known. The objective is to decide the speeds of machines and minimize the makespan of the schedule among all the feasible choices. The problem is motivated by some practical application scenarios. This problem is strongly NP-hard in general, and we discuss various cases of it. In particular, we obtain a polynomial time algorithm when there is one linear constraint. If the number of constraints is more than one and the number of machines is a fixed constant, then we give a $$(2+\epsilon )$$ -approximation algorithm. For the case where the number of machines is an input of the problem instance, we propose several approximation algorithms, and obtain a PTAS when the number of distinct machine speeds is a fixed constant.

We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph. We then show a greedy algorithm to reduce the number of singleton-job layers, resulting in an improved partition, which leads to a 4/3-approximation. Both approximation algorithms apply to the general m-machine open-shops too.

Let there be a set J of n jobs and a set M of m parallel machines, where each job j takes $$p_{i,j} \in \mathbb {Z}^+$$ time units on machine i and assume $$p_{i,j}=\infty $$ implies job j cannot be scheduled on machine i. In makespan minimization on unrelated parallel machines ( $$R||C_{max}$$ ), the goal is to schedule each job non-preemptively on a machine so as to minimize the makespan. A job-intersection graph $$G_J=(J,E_J)$$ is an unweighted undirected graph where there is an edge $$\{j,j'\} \in E_J$$ if there is a machine i such that both $$p_{i,j}\ne \infty $$ and $$p_{i,j'} \ne \infty $$ . In this paper we consider two variants of $$R||C_{max}$$ where there are a small number of eligible jobs per machine. First, we prove that there is no approximation algorithm with approximation ratio better than 3/2 for $$R||C_{max}$$ when restricted to instances where the job-intersection graph contains no diamonds, unless . Second, we match this lower bound by presenting a 3/2-approximation algorithm for this special case of $$R||C_{max}$$ , and furthermore show that when $$G_J$$ is triangle free $$R||C_{max}$$ is solvable in polynomial time. For $$R||C_{max}$$ restricted to instances when every machine can process at most $$\ell $$ jobs, we give approximation algorithms with approximation ratios 3/2 and 5/3 for $$\ell =3$$ and $$\ell =4$$ respectively, a polynomial-time algorithm when $$\ell =2$$ , and prove that it is -hard to approximate the optimum solution within a factor less than 3/2 when $$\ell \ge 3$$ . In the special case where every $$p_{i,j} \in \{p_j, \infty \}$$ , called the restricted assignment problem, and there are only two job lengths $$p_j \in \{\alpha ,\beta \}$$ we present a $$(2-1/(\ell -1))$$ -approximation algorithm when $$\ell \ge 3$$ .

The Student-Project Allocation problem with lecturer preferences over Students ( ) involves assigning students to projects based on student preferences over projects, lecturer preferences over students, and the maximum number of students that each project and lecturer can accommodate. This classical model assumes that preference lists are strictly ordered. Here, we study a generalisation of where ties are allowed in the preference lists of students and lecturers, which we refer to as the Student-Project Allocation problem with lecturer preferences over Students with Ties ( ). We investigate stable matchings under the most robust definition of stability in this context, namely super-stability. We describe the first polynomial-time algorithm to find a super-stable matching or to report that no such matching exists, given an instance of . Our algorithm runs in O(L) time, where L is the total length of all the preference lists. Finally, we present results obtained from an empirical evaluation of the linear-time algorithm based on randomly-generated instances. Our main finding is that, whilst super-stable matchings can be elusive, the probability of such a matching existing is significantly higher if ties are restricted to the lecturers’ preference lists.

In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets $$\mathcal S \subseteq 2^E$$ , a cost $$w_S$$ on each set $$S\in \mathcal S$$ , a covering requirement $$r_e$$ for each element $$e\in E$$ , and an integer k, the goal is to find a sub-collection $$\mathcal F \subseteq \mathcal S$$ to fully cover at least k elements such that the cost of $$\mathcal F$$ is as small as possible, where element e is fully covered by $$\mathcal F$$ if it belongs to at least $$r_e$$ sets of $$\mathcal F$$ . On the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor $$O(n^\frac{1}{2(\log \log n)^c})$$ under the ETH assumption. A primal dual algorithm for MinPSMC is presented with a guaranteed performance ratio $$O(\sqrt{n})$$ when $$r_{\max }$$ and f are constants, where $$r_{\max } =\max _{e\in E} r_e$$ is the maximum covering requirement and f is the maximum frequency of elements (that is the maximum number of sets containing a common element). We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure.

Predicate abstraction technique makes boolean programs a simple and popular model for program verification, of which the state reachability problem is decidable. However, the existing approach to reachability analysis of a concurrent boolean program, by applying the backward search (BWS) algorithm to the thread transition diagram (TTD) of the program, is of high complexity. To accelerate this approach, a method that expands the TTD with a kind of expansion edges and summarizes each path in the expanded TTD into a set of Presburger formulas has been proposed, so that the reachability problem is reduced to the satisfiability of the summary formulas. In this paper, we present a method for reachability analysis of concurrent boolean programs which improves the existing work in two aspects. First, with refined constraints on edge expansion, only a small number of expansion edges are required to be added to the TTD, which reduces the space consumption. Second, with optimized algorithm of path summarization using counter abstraction, less local state counters are dealt with and less summary formulas are generated. We have implemented the method and evaluated it on a large set of benchmark concurrent boolean programs. Experimental results show its efficiency on summarization and verification.

We study the Robust Assignment Problem where the goal is to assign items of various types to containers without exceeding container capacity. We seek an assignment that uses the fewest number of containers and is robust, that is, if any item of type $$t_i$$ becomes corrupt causing the containers with type $$t_i$$ to become unstable, every other item type $$t_j \ne t_i$$ is still assigned to a stable container. We begin by presenting an optimal polynomial-time algorithm that finds a robust assignment using the minimum number of containers for the case when the containers have infinite capacity. Then we consider the case where all containers have some fixed capacity and give an optimal polynomial-time algorithm for the special case where each type of item has the same size. When the sizes of the item types are nonuniform, we provide a polynomial-time 2-approximation for the problem. We also prove that the approximation ratio of our algorithm is no lower than 1.813. We conclude with an experimental evaluation of our algorithm.

The and problems are well-known problems in computer science. In this paper, we consider versions of both of these problems - and . For both problems, the input is a set of geometric objects $$\mathcal {O}$$ and a set of points $$\mathcal {P}$$ in the plane. In the MDIS problem, the objective is to find a maximum size subset $$\mathcal {O}^\prime \subseteq \mathcal {O}$$ of objects such that no two objects in $$\mathcal {O}^\prime $$ have a point in common from $$\mathcal {P}$$ . On the other hand, in the MDDS problem, the objective is to find a minimum size subset $$\mathcal {O}^\prime \subseteq \mathcal {O}$$ such that for every object $$O \in \mathcal {O} \setminus \mathcal {O}^\prime $$ there exists at least one object $$O^\prime \in \mathcal {O}^\prime $$ such that $$O\,\cap \,O^\prime $$ contains a point from $$\mathcal {P}$$ .In this paper, we present $$\mathsf {PTAS}$$ es based on technique for both MDIS and MDDS problems, where the objects are arbitrary radii disks and arbitrary side length axis-parallel squares. Further, we show that the MDDS problem is $$\mathsf {APX}$$ -hard for axis-parallel rectangles, ellipses, axis-parallel strips, downward shadows of line segments, etc. in $$\mathbb {R}^2$$ and for cubes and spheres in $$\mathbb {R}^3$$ . Finally, we prove that both MDIS and MDDS problems are $$\mathsf {NP}$$ -hard for unit disks intersecting a horizontal line and for axis-parallel unit squares intersecting a straight line with slope $$-1$$ .

In COCOA 2015, Korman et al. studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be $$\mathsf {NP}$$ -hard, even if the line segments in S are axis-parallel, and it remains $$\mathsf {NP}$$ -hard when the goal is cover the “rectangular” cells (i.e., cells that are defined by exactly four axis-parallel line segments).In this paper, we consider the approximability of the problem. We first give a $$\mathsf {PTAS}$$ for the problem when the line segments in S are in any orientation, but we can only select the covering line segments from one orientation. Then, we show that when the goal is to cover the rectangular cells using line segments from both horizontal and vertical line segments, then the problem is $$\mathsf {APX}$$ -hard. We also consider the parameterized complexity of the problem and prove that the problem is $$\mathsf {FPT}$$ when parameterized by the size of an optimal solution. Our $$\mathsf {FPT}$$ algorithm works when the line segments in S have two orientations and the goal is to cover all cells, complementing that of Korman et al. [9] in which the goal is to cover the “rectangular” cells.

This paper investigates the Score-Constrained Strip-Packing Problem (SCSPP), a combinatorial optimisation problem that generalises the one-dimensional bin-packing problem. In the construction of cardboard boxes, rectangular items are packed onto strips to be scored by knives prior to being folded. The order and orientation of the items on the strips determine whether the knives are able to score the items correctly. Initially, we detail an exact polynomial-time algorithm for finding a feasible alignment of items on a single strip. We then integrate this algorithm with a packing heuristic to address the multi-strip problem and compare with two other greedy heuristics, discussing the circumstances in which each method is superior.

This paper proposes a new algorithm for reducing Approximate Nearest Neighbor problem to Approximate Near Neighbor problem. The advantage of this algorithm is that it achieves $$O(\log {n})$$ query time. As a reduction problem, the query time complexity is the times of invoking the algorithm for Approximate Near Neighbor problem. All former algorithms for the same reduction need polylog(n) query time. A box split method proposed by Vaidya is used in our paper to achieve the $$O(\log {n})$$ query time complexity.

Given a set of points P in the Euclidean plane, the classic problem of convex hull in computational geometry asks to compute the smallest convex polygon C with the vertex set $$X \subseteq P$$ , such that every point in P belongs to C.In our knowledge, only two map-reduce convex hull algorithms have been designed so far. The exact map-reduce algorithm designed by Goodrich et al. (2011) is intricate and runs in constant number of rounds when the mappers and reducers have a memory of $$\varTheta (|P|^\epsilon )$$ , for a small constant $$\epsilon >0$$ . Otherwise, their algorithm runs in logarithmic number of rounds with high probability. In Big Data, easy-to-implement constant-round map-reduce algorithms are highly preferred. The other exact map-reduce algorithm, designed by Eldawy et al. (2011), does not perform efficiently when X contains sufficiently high number of points from P.In this paper, we design two new simple constant-round map-reduce algorithms along with map-reduce implementable pruning heuristics to address the above shortcomings. Our first algorithm CH-MR is exact and outperforms Eldawy et al.’s algorithm when reasonable computing resources are available, and the heuristics are able to prune away sufficient number of points. The second algorithm, named APXCH-MR, can run efficiently on any point set to return an approximate convex hull, when the input parameters are sub-linear in |P|.The designed algorithms are theoretically analyzed in the light of the popular $$\mathcal {MRC}$$ model. Our algorithms are easy to implement and do not use any complicated data structure.

In this paper, we introduce the problem of transmitting particles to a target point by the effect of a repulsion actuator (RA). In this problem, we are given a polygonal domain P and a target point t inside it. Also, there is a particle at each point of P. The question is which particles can get to the target point t by activating a RA in P. We present the first polynomial time algorithm to solve this problem.

Most path planning problems among polygonal obstacles ask to find a path that avoids the obstacles and is optimal with respect to some measure or a combination of measures, for example an u-to-v shortest path of clearance at least c, where u and v are points in the free space and c is a positive constant. In practical applications, such as emergency interventions/evacuations and medical treatment planning, a number of u-to-v paths are suggested by experts and the question is whether such paths satisfy specific requirements, such as a given clearance from the obstacles. We address the following path query problem: Given a set S of m disjoint simple polygons in the plane, with a total of n vertices, preprocess them so that for a query consisting of a positive constant c and a simple polygonal path $$\pi $$ with k vertices, from a point u to a point v in free space, where k is much smaller than n, one can quickly decide whether $$\pi $$ has clearance at least c (that is, there is no polygonal obstacle within distance c of $$\pi $$ ). To do so, we show how to solve the following related problem: Given a set S of m simple polygons in $$\mathfrak {R}^{2}$$ , preprocess S into a data structure so that the polygon in S closest to a query line segment s can be reported quickly. We present an $$O(t \log n)$$ time, O(t) space preprocessing, $$O((n / \sqrt{t}) \log ^{7/2} n)$$ query time solution for this problem, for any $$n ^{1 + \epsilon } \le t \le n^{2}$$ . For a path with k segments, this results in $$O((n k / \sqrt{t}) \log ^{7/2} n)$$ query time, which is a significant improvement over algorithms that can be derived from existing computational geometry methods when k is small.

We consider an optimization problem posed by an actual newspaper company, which consists of computing a minimum length route for a delivery truck, such that the driver only stops at street crossings, each time delivering copies to all customers adjacent to the crossing. This can be modeled as an abstract problem that takes an unweighted simple graph $$G = (V, E)$$ and a subset of edges X and asks for a shortest cycle, not necessarily simple, such that every edge of X has an endpoint in the cycle.We show that the decision version of the problem is strongly NP-complete, even if G is a grid graph. Regarding approximate solutions, we show that the general case of the problem is APX-hard, and thus no PTAS is possible unless $$ P = NP $$ . Despite the hardness of approximation, we show that given any $$\alpha $$ -approximation algorithm for metric TSP, we can build a $$3\alpha $$ -approximation algorithm for our optimization problem, yielding a concrete 9 / 2-approximation algorithm.The grid case is of particular importance, because it models a city map or some part of it. A usual scenario is having some neighborhood full of customers, which translates as an instance of the abstract problem where almost every edge of G is in X. We model this property as $$|E - X| = o(|E|)$$ , and for these instances we give a $$(3/2 + \varepsilon )$$ -approximation algorithm, for any $$\varepsilon > 0$$ , provided that the grid is sufficiently big.

This paper investigates the impact that task difficulty and crowd composition have on the success of the Wisdom of Artificial Crowds metaheuristic. The metaheuristic, which is inspired by the wisdom of crowds phenomenon, combines the intelligence from a group of optimization searches to form a new solution. Unfortunately, the aggregate formed by the metaheuristic is not always better than the best individual solution within the crowd, and little is known about the variables which maximize the metaheuristic’s success. Our study offers new insights into the influential factors of artificial crowds and the collective intelligence of multiple optimization searches performed on the same problem. The results show that favoring the opinions of experts (i.e., the better searches) improves the chances of the metaheuristic succeeding by more than 15% when compared to the traditional means of equal weighting. Furthermore, weighting expertise was found to require smaller crowd sizes for the metaheuristic to reach its peak chances of success. Finally, crowd size was discovered to be a critical factor, especially as problem complexity grows or average crowd expertise declines. However, crowd size matters only up to a point, after which the probability of success plateaus.

Sorting is studied in this paper as an archetypal example to explore the optimizing power of consensus. In conceptualizing the consensus sort, the classical hill-climbing method of optimization is paired with the modern notion that value and fitness can be judged by data mining. Consensus sorting is a randomized sorting algorithm which is based on randomly selecting pairs of elements within an unsorted list (expressed in this paper as a permutation), and deciding whether to swap them based on appeals to a database of other permutations. The permutations in the database are all scored via some adaptive sorting metric, and the decision to swap depends on whether the database consensus suggests a better score as a result of swapping. This uninformed search process does not require the definition of the concept of sorting, but rather a depends on selecting a metric which does a good job of distinguishing a good path to the goal, a sorted list. A previous paper has shown that the ability of the algorithm to converge on the goal depends strongly on the metric which is used, and analyzed the performance of the algorithm when number of inversions was used as a metric. This paper continues by analyzing the performance of a much more efficient metric, the number of cycles in the permutation.

The k-Canadian Traveller Problem ( $$k$$ -CTP), proven PSPACE-complete by Papadimitriou and Yannakakis, is a generalization of the Shortest Path Problem which admits blocked edges. Its objective is to determine the strategy that makes the traveller traverse graph G between two given nodes s and t with the minimal distance, knowing that at most k edges are blocked. The traveller discovers that an edge is blocked when arriving at one of its endpoints.We study the competitiveness of randomized memoryless strategies to solve the $$k$$ -CTP. Memoryless strategies are attractive in practice as a decision made by the strategy for a traveller in node v of G does not depend on his anterior moves. We establish that the competitive ratio of any randomized memoryless strategy cannot be better than $$2k + O\left( 1\right) $$ . This means that randomized memoryless strategies are asymptotically as competitive as deterministic strategies which achieve a ratio $$2k+1$$ at best.

In this paper, we extend the Rent Sharing problem to the case that every room must be allocated to a group of agents. In the classic Rent Sharing problem, there are n agents and a house with n rooms. The goal is to allocate one room to each agent and assign a rent to each room in a way that no agent envies any other option. Our setting deviates from the classic Rent Sharing problem in a sense that the rent charged to each room must be divided among the members of the resident group.We define three notions to evaluate fairness, namely, weak envy-freeness, aggregate envy-freeness and strong envy-freeness. We also define three different policies to divide the cost among the group members, namely, equal, proportional, and free cost-sharing policies.We present several positive and negative results for different combinations of the fairness criteria and rent-division policies. Specifically, when the groups are pre-determined, we propose a strong envy-free solution that allocates the rooms to the agents, with free cost-sharing policy. In addition, for the case that the groups are not pre-determined, we propose a strong envy-free allocation algorithm with equal cost-sharing policy. We leverage our results to obtain an algorithm that determines the maximum total rent along with the proper allocation and rent-division method.

In this paper, we propose a new data structure sequence sentential decision diagram (SSDD) that represents sets of strings. SSDD is a generalized data structure of Sequence Binary Decision Diagram (SeqBDD), that is a similar data structure to a deterministic finite automaton, but the size can be exponentially smaller than the SeqBDD for the same string set. We also provide algorithms to manipulate sets of strings on SSDD. These algorithms allow operations such as intersection, union, and concatenation to be executed on SSDDs under their compressed representations without expanding. We analyzed the size complexity of SSDD and the time complexity of proposed algorithms.

We revisit the online Unit Covering problem in higher dimensions: Given a set of n points in $$\mathbb {R}^d$$ , that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in $$\mathbb {R}^d$$ using Euclidean distance. The current best competitive ratio of an online algorithm, $$O(2^d d \log {d})$$ , is due to Charikar et al. (2004); their algorithm is deterministic. (I) We give an online deterministic algorithm with competitive ratio $$O(1.321^d)$$ , thereby improving on the earlier record by an exponential factor. In particular, the competitive ratios are 5 for the plane and 12 for 3-space (the previous ratios were 7 and 21, respectively). For $$d=3$$ , the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm (with an adaptive deterministic adversary) for Unit Covering in $$\mathbb {R}^d$$ under the $$L_{2}$$ norm is at least $$d+1$$ for every $$d \ge 1$$ . This greatly improves upon the previous best lower bound, $$\varOmega (\log {d} / \log {\log {\log {d}}})$$ , due to Charikar et al. (2004). (III) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online Unit Covering in $$\mathbb {R}^2$$ and respectively $$\mathbb {R}^3$$ ; the previous best lower bounds were both 3. (IV) When the input points are taken from the square or hexagonal lattices in $$\mathbb {R}^2$$ , we give deterministic online algorithms for Unit Covering with an optimal competitive ratio of 3.

In the k-terminal cut problem, we are given a graph with edge weights and k distinct vertices called “terminals.” The goal is to remove a minimum weight collection of edges from the graph such that there is no path between any pair of terminals. The k-terminal cut problem is NP-hard.The k-terminal cut problem has been extensively studied and a number of algorithms have been devised for it. Most of the algorithms devised for the problem are approximation algorithms or heuristic algorithms. There are also fixed-parameter tractable algorithms that solve the problem optimally in time that is polynomial when the value of the optimum is fixed, but none have been shown empirically practical. It is possible to apply implicit enumeration using any integer programming formulation of the problem and solve it with a branch-and-bound algorithm.Here, we present a branch-and-bound algorithm for the k-terminal cut problem which does not rely on an integer programming formulation. Our algorithm employs “isolating cuts” and, for this reason, we call our branch-and-bound algorithm Isolation Branching.In an empirical experiment, we compare the performance of the Isolation Branching algorithm to that of a branch-and-bound applied to the strongest known integer programming formulation of k-terminal cut. The integer programming branch-and-bound procedure is implemented with Gurobi, a commercial mixed-integer programming solver. We compare the performance of the two approaches for real-world instances and synthetic data. The results on real data indicate that Isolation Branching, coded in Python, runs an order of magnitude faster than Gurobi for problems of sizes of up to tens of thousands of vertices and hundreds of thousands of edges. Our results on synthetic data also indicate that Isolation Branching scales more effectively.Though we primarily focus on creating a practical tool for k-terminal cut, as a byproduct of our algorithm we prove that the complexity of Isolation Branching is also fixed-parameter tractable with respect to the size of the optimal solution, thus providing an alternative, constructive, and somewhat simpler, proof of this fact.

2-ultrametrics are a generalization of the ultrametrics and it is known that there is a one-to-one correspondence between the set of 2-ultrametrics and the set of indexed 2-hierarchies (which are a generalization of indexed hierarchies). Cycle-complete dissimilarities, recently introduced by Trudeau, are a generalization of ultrametrics and form a subset of the 2-ultrametrics; therefore the set of cycle-complete dissimilarities corresponds to a subset of the indexed 2-hierarchies. In this study, we characterize this subset as the set of indexed acyclic 2-hierarchies, which in turn allows us to characterize the cycle-complete dissimilarities. In addition, we present an O $$(n^2\log n)$$ time algorithm that, given an arbitrary cycle-complete dissimilarities of order n, finds the corresponding indexed acyclic 2-hierarchy.

Multiple RNA interaction can be modeled as a problem in combinatorial optimization, where the “optimal” structure is driven by an energy-minimization-like algorithm. However, the actual structure may not be optimal in this computational sense. Moreover, it is not necessarily unique. Therefore, alternative sub-optimal solutions are needed to cover the biological ground.We extend a recent combinatorial formulation for the Multiple RNA Interaction problem with approximation algorithms to handle more elaborate interaction patterns, which when combined with Gibbs sampling and MCMC (Markov Chain Monte Carlo), can efficiently generate a reasonable number of optimal and sub-optimal solutions. When viable structures are far from an optimal solution, exploring dependence among different parts of the interaction can increase their score and boost their candidacy for the sampling algorithm. By clustering the solutions, we identify few representatives that are distinct enough to suggest possible alternative structures.

Given a set P of n locations on which facilities can be placed and an integer k, we want to place k facilities on some locations so that a designated objective function is maximized. The problem is called the k-dispersion problem.In this paper we give a simple O(n) time algorithm to solve the max-min version of the k-dispersion problem if P is a set of points on a line. This is the first O(n) time algorithm to solve the max-min k-dispersion problem for the set of “unsorted” points on a line.If P is a set of sorted points on a line, and the input is given as an array in which the coordinates of the points are stored in the sorted order, then by slightly modifying the algorithm above one can solve the dispersion problem in $$O(\log n)$$ time. This is the first sublinear time algorithm to solve the max-min k-dispersion problem for the set of sorted points on a line.

Graph pebbling, as introduced by Chung, is a two-player game on a graph G. Player one distributes “pebbles” to vertices and designates a root vertex. Player two attempts to move a pebble to the root vertex via a sequence of pebbling moves, in which two pebbles are removed from one vertex in order to place a single pebble on an adjacent vertex. The pebbling number of a simple graph G is the smallest number $$\pi _G$$ such that if player one distributes $$\pi _G$$ pebbles in any configuration, player two can always win. Computing $$\pi _G$$ is provably difficult, and recent methods for bounding $$\pi _G$$ have proved computationally intractable, even for moderately sized graphs.Graham conjectured that the pebbling number of the Cartesian-product of two graphs G and H, denoted $$G\,\square \,H$$ , is no greater than $$\pi _G \pi _H$$ . Graham’s conjecture has been verified for specific families of graphs; however, in general, the problem remains open.This study combines the focus of developing a computationally tractable method for generating good bounds on $$\pi _{G \,\square \, H}$$ , with the goal of providing evidence for (or disproving) Graham’s conjecture. In particular, we present a novel integer-programming (IP) approach to bounding $$\pi _{G \,\square \, H}$$ that results in significantly smaller problem instances compared with existing IP approaches to graph pebbling. Our approach leads to a sizable improvement on the best known bound for $$\pi _{L \,\square \, L}$$ , where L is the Lemke graph. $$L\,\square \, L$$ is among the smallest known potential counterexamples to Graham’s conjecture.

Resilience, as an potential explanation of a specified query, plays a fundamental and important role in query explanation, database debugging and error tracing. Resilience decision problem is defined on a database d, given a boolean query q where q(d) is initially true, and an integer k, it is to determine if there exists a tuple set $$\varDelta $$ such that size of $$\varDelta $$ is no more than k and query result $$q(d\oplus \varDelta )$$ becomes false, where $$\oplus $$ can be deletion or insertion operation. Results of this problem on relational algebraic queries have been showed in previous work. However, we revisit this decision problem on aggregation queries in the light of the parametric refinement of complexity theory, provide new results. We show that, this problem is intractable on nested COUNT and SUM query both under data complexity and parametric complexity.

Doodle polls allow people to schedule meetings or events based on time preferences of participants. Each participant indicates on a web-based poll form which time slots they find acceptable and a time slot with the most votes is chosen. This is a social choice mechanism known as approval voting, in which a standard assumption is that all voters vote sincerely—no one votes “no” on a time slot they prefer to a time slot they have voted “yes” on. We take a game-theoretic approach to understanding what happens in Doodle polls assuming participants vote sincerely. First we characterize Doodle poll instances where sincere pure Nash Equilibria (NE) exist, both under lexicographic tie-breaking and randomized tie-breaking. We then study the quality of such NE voting profiles in Doodle polls, showing the price of anarchy and price of stability are both unbounded, even when a time slot that many participants vote yes for is selected. Finally, we find some reasonable conditions under which the quality of the NE (and strong NE) is good.

We introduce and study a variant of network cost-sharing games with additional non-shareable costs (NCSG+), which is shown to possess a pure Nash equilibrium (PNE). We extend polynomial-time PNE computation results to a class of graphs that generalizes series-parallel graphs when the non-shareable costs are player-independent. Further, an election game model is presented based on an NCSG+ when voter opinions form natural discrete clusters. This model captures several variants of the classic Hotelling-Downs election model, including ones with limited attraction, ability of candidates to enter, change stance positions and exit any time during the campaign or abstain from the race, the restriction on candidates to access certain stance positions, and the operational costs of running a campaign. Finally, we provide a polynomial-time PNE computation for an election game when stance changes are restricted.

Wireless sensor networks have been widely used in environment, climate, animal monitoring, surveillance, and also in the medical field. When deploying sensors to monitor boundaries of battlefields or country borders, sensors are usually dispersed from an aircraft following a predetermined path. In such scenarios sensing gaps are usually unavoidable. We consider a wireless network consisting of randomly deployed sensor nodes and directional border nodes deployed using a random line-based deployment model. In this paper we propose an adaptive distributed algorithm for weak-barrier coverage that allows border nodes to dynamically compute their orientation based on notifications from the sensor nodes, such that to increase the number of intruders detected by the border nodes. We use simulations to analyze the performance of our algorithm and to compare it with a non-adaptive gap mending algorithm.