Combinatorial Optimization and Applications

We study the problem of fully mitigating the effects of denial of service by filtering the minimum necessary set of the undesirable flows. First, we model this problem and then we concentrate on a subproblem where every good flow has a bottleneck. We prove that unless $$\text {P}= \text {NP}$$P=NP, this subproblem is inapproximable within factor $$2^{\log ^{1 - 1/\log \log ^c (n)}(n)}$$2log1-1/loglogc(n)(n), for $$n = \left| E \right| + \left| GF \right| $$n=E+GF and any $$c < 0.5$$c<0.5. We provide a $$b (k + 1)$$b(k+1)-factor polynomial approximation, where k bounds the number of the desirable flows that a desirable flow intersects, and b bounds the number of the undesirable flows that can intersect a desirable one at a given edge. Our algorithm uses the local ratio technique.

Storage overflow problem in wireless sensor networks is a new and challenging issue, wherein data-collecting base station is not available while more data items are generated than available storage space in the entire network. In this paper, we consider overall storage overflow problem in WSNs, the goal of which is to maximize the minimum remaining energy of data node (the node with overflow data) in order to prolong the lifetime of the sensor network. For overall storage overflow problem, we propose a two-step solution. A degree-constrained data aggregation algorithm is presented, and then we further propose a data replication algorithm which is a unified method, integrating data aggregation and data redistribution. Extensive simulations show that our proposed algorithms significantly outperform than existing algorithms especially in extending the lifetime of the sensor network.

Given an axis-aligned rectangle R and a set P of n points in the proper inside of R we wish to partition R into a set S of $$n+1$$ n+1 rectangles so that each point in P is on the common boundary between two rectangles in S. We call such a partition of R a feasible floorplan of R with respect to P. Intuitively P is the locations of columns and a feasible floorplan is a floorplan in which no column is in the proper inside of a room, i.e., columns are allowed to be placed only on the partition walls between rooms. In this paper we give an efficient algorithm to enumerate all feasible floorplans of R with respect to P. The algorithm is based on the reverse search method, and enumerates all feasible floorplans in $$O(|S_P|)$$ O(|SP|) time using O(n) space where $$S_P$$ SP is the set of the feasible floorplans of R with respect to P, while the known algorithms need either $$O(n|S_P|)$$ O(n|SP|) time and O(n) space or $$O(\log n |S_P|)$$ O(logn|SP|) time and $$O(n^3)$$ O(n3) space.

Constructing vertex-disjoint spanning trees (VDSTs for short) of a given network is an important issue in the research of network fault-tolerance and security. The star network was proposed as an attractive interconnection network model for competing with n-cube. Accordingly, Rescigno in [Inform. Sci. 137 (2001) 259–276] proposed an algorithm to construct $$n-1$$n-1 VDSTs rooted at a common node in an n-dimensional star network $$S_n$$Sn. In this paper, we point out that there exists a flaw in Rescigno’s algorithm, and thus the spanning trees constructed by this algorithm may not be vertex-disjoint. As a result, a correct scheme of constructing $$n-1$$n-1 VDSTs on $$S_n$$Sn is presented. Moreover, based on the reversing rule of building certain paths of VDSTs in the amendatory scheme, we propose a new algorithm to construct $$n-1$$n-1 VDSTs with optimal heights on $$S_n$$Sn. In particular, the proposed algorithm is more efficient and can easily be implemented in parallel.

A protein-protein interaction (PPI) network is an unweighted and undirected graph representing the interactions among proteins, where each node denotes a protein and each edge connecting two nodes indicates their interaction. Given two PPI networks, finding their alignment is a fundamental problem and has many important applications in bioinformatics. However, it often needs to solve some generalized version of subgraph isomorphism problem which is challenging and NP-hard. Following our previous geometric approach [21], we propose a unified algorithmic framework for PPI networks alignment. We first define a general concept called “Protein Mover’s Distance (PMD)” to evaluate the alignment of two PPI networks. PMD is similar to the well known “Earth Mover’s Distance”; however, we also incorporate some other information, e.g., the functional annotation of proteins. Our algorithmic framework consists of two steps, Embedding and Matching. For the embedding step, we apply three different graph embedding techniques to preserve the topological structures of the original PPI networks. For the matching step, we compute a rigid transformation for one of the embedded PPI networks so as to minimize its PMD to the other PPI network; by using the flow values of the resulting PMD as the matching scores, we are able to obtain the desired alignment. Also, our framework can be easily extended to joint alignment of multiple PPI networks. The experimental results on two popular benchmark datasets suggest that our method outperforms existing approaches in terms of the quality of alignment.

Crowd sensing is a novel sensing paradigm, in which a challenging task is to balance benefits of various participants, i.e., data requesters, data providers and transaction platforms for attracting sufficient participants. Little attention in literature has been paid to the transaction platform’s profit which is one of the major issues for maintaining a crowd sensing system consistently. In this paper, we aim to propose a mechanism design for optimizing the platform’s profit. For that, we first model the interactions in crowd sensing by leveraging tools of game theory, and then we prove the best strategy for maximizing the benefit of transaction platforms with satisfying individual rationality constraint and incentive compatibility constraint. Finally, we propose two practical algorithms based on the best strategy. Our simulations show that the algorithms are effective in terms of keeping the platform’s profit and time efficiency.

This paper investigates the problem of maximum stacking base pairs from RNA secondary structure prediction. The basic version of maximum stacking base pairs problem as: given an RNA sequence, to find a maximum number of base pairs where each base pair is involved in a stacking. Ieong et al. showed this problem to be NP-hard, where the candidate base pairs follow some biology principle and are given implicitly. In this paper, we study the version of this problem that the candidate base pairs are given explicitly as input, and present a new approximation algorithm for this problem by the local search method, improving the approximation factor from 5/2 to 7/3. The time complexity is within $$O(n^{14})$$O(n14), since we adopt 1-substitution and special 2-substitutions in the local improvement steps.

The stacker crane problem is treated as one modified arc routing problem. This problem is to find some route for stacker cranes on a construction site such that all arcs in a mixed graph $$G=(V,E\cup A;w)$$G=(V,E∪A;w) must be traversed at least once. In the real literature, since many different building materials must be handled, we consider the generalized stacker crane (GSC) problem, and the objective of this new problem is to determine a minimum weighted tour C traversing each arc e (in A) a number of times between the lower demand and upper demand.In this paper, we design two approximation algorithms for the GSC problem. The first algorithm uses some exact algorithm to solve the integral circulation problem, and the second algorithm uses some approximation algorithm to solve the metric traveling salesman problem. Combining these two approximation algorithms, we can design a 9/5-approximation algorithm to solve the GSC problem.

Given an integer $$L\in \mathbb {Z}^{+}$$L∈Z+ and an undirected graph with a weight and a length associated with every edge, the constrained minimum spanning tree (CMST) problem is to compute a minimum weight spanning tree with total length bounded by L. The problem was shown weakly $$\mathcal{NP}$$NP-hard in [1], admitting a PTAS with a runtime $$O(n^{O(\frac{1}{\epsilon })}(m\log ^{2}n+n\log ^{3}n))$$O(nO(1ϵ)(mlog2n+nlog3n)) due to Ravi and Goemans [13]. In the paper, we present an exact algorithm for CMST, based on our developed bicameral edge replacement which improves a feasible solution of CMST towards an optimal solution. By applying the classical rounding and scaling technique to the exact algorithm, we can obtain a fully polynomial-time approximation scheme (FPTAS), i.e. an approximation algorithm with a ratio $$(1+\epsilon )$$(1+ϵ) and a runtime $$O(mn^{5}\frac{1}{\epsilon ^{2}})$$O(mn51ϵ2), where $$\epsilon >0$$ϵ>0 is any fixed real number.

In this paper, we identify a novel problem Trajectory-Based Relay Deployment (TBRD) which aims at maximizing user connection time as the users roam through the target area while complying with relay resource constraints. To solve the TBRD, we first propose the concept Demand Nodes (DNs). Next, we design a Demand Node Generation (DNG) algorithm that transforms the continuous historical user trajectory into a number of discrete DNs. By generating DNs, we convert the TBRD problem into a Demand Node Coverage (DNC) problem, which is NP-complete. After that, we design an approximation algorithm, named Submodular Iterative Deployment Algorithm (SIDA), to solve the DNC problem with the approximation factor $$1-\frac{1}{\sqrt{e\cdot (1-1/k)}}$$1-1e·(1-1/k). The simulation on five real datasets shows that our algorithm can obtain high coverage for users in motion, leading to better user experience.

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem (SMFLP) and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set $$\mathcal {C}$$C and a facility set $$\mathcal {F} $$F from a metric space, a facility opening cost $$f_i \ge 0$$fi≥0 for each $$ i \in \mathcal {F}$$i∈F, and an integer k. The goal is to open a facility subset $$F \subseteq \mathcal {F}$$F⊆F with $$ |F| \le k$$|F|≤k and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.

In this paper, we investigate the spectrum assignment (SA) problem in chain and ring topologies, which is the key network design and control problem in spectrum sliced elastic optical path network. Improved algorithms with guaranteed performance ratios are provided for several NP-hard scenarios of the SA problem. Concretely, we develop $$\frac{4}{3}$$43-approximation algorithms for the SA problem in chain networks with five or six nodes, and for the SA problem in the clockwise direction of a bidirectional ring networks with five nodes. For the latter problem with six nodes, we propose a $$\frac{3}{2}$$32-approximation algorithm. All the algorithms are combinatorial and constructive, whose performance ratios are strictly smaller than the best known ones to date.

For positive integers k and $$\lambda $$λ, a graph G is $$(k,\lambda )$$(k,λ)-connected if it satisfies the following two conditions: (1) $$|V(G)|\ge k+1$$|V(G)|≥k+1, and (2) for any subset $$S\subseteq V(G)$$S⊆V(G) and any subset $$L\subseteq E(G)$$L⊆E(G) with $$\lambda |S|+|L|<k\lambda $$λ|S|+|L|<kλ, $$G-(S\cup L)$$G-(S∪L) is connected. For positive integers k and $$\ell $$ℓ, a graph G with $$|V(G)|\ge k+\ell +1$$|V(G)|≥k+ℓ+1 is said to be $$(k,\ell )$$(k,ℓ)-mixed-connected if for any subset $$S\subseteq V(G)$$S⊆V(G) and any subset $$L\subseteq E(G)$$L⊆E(G) with $$|S|\le k, |L|\le \ell $$|S|≤k,|L|≤ℓ and $$|S|+|L|<k+\ell $$|S|+|L|<k+ℓ, $$G-(S\cup L)$$G-(S∪L) is connected. In this paper, we investigate the $$(k,\lambda )$$(k,λ)-connectivity and $$(k,\ell )$$(k,ℓ)-mixed-connectivity of random graphs, and generalize the results of Erdős and Rényi (1959), and Stepanov (1970). Furthermore, our argument can show that in the random graph process $$\tilde{G} = \left( {{G_t}} \right) _0^N $$G~=Gt0N, $$N=\left( {\begin{array}{c}n\\ 2\end{array}}\right) $$N=n2, the hitting times of minimum degree at least $$k\lambda $$kλ and of $$G_t$$Gt being $$(k,\lambda )$$(k,λ)-connected coincide with high probability, and also the hitting times of minimum degree at least $$k+\ell $$k+ℓ and of $$G_t$$Gt being $$(k,\ell )$$(k,ℓ)-mixed-connected coincide with high probability. These results are analogous to the work of Bollobás and Thomassen (1986) on classic connectivity.

A path in an edge-colored graph is called conflict-free if it contains a color that is used by exactly one of its edges. An edge-colored graph G is conflict-free connected if for any two distinct vertices of G, there is a conflict-free path connecting them. For a connected graph G, the conflict-free connection number of G, denoted by cfc(G), is defined as the minimum number of colors that are required to make G conflict-free connected. In this paper, we investigate the conflict-free connection numbers of connected claw-free graphs, especially line graphs. We use L(G) to denote the line graph of a graph G. In general, the k-iterated line graph of a graph G, denoted by $$L^k(G)$$Lk(G), is the line graph of the graph $$L^{k-1}(G)$$Lk-1(G), where $$k\ge 2$$k≥2 is a positive integer. We first show that for an arbitrary connected graph G, there exists a positive integer k such that $$cfc(L^k(G))\le 2$$cfc(Lk(G))≤2. Secondly, we get the exact value of the conflict-free connection number of a connected claw-free graph, especially a connected line graph. Thirdly, we prove that for an arbitrary connected graph G and an arbitrary positive integer k, we always have $$cfc(L^{k+1}(G))\le cfc(L^k(G))$$cfc(Lk+1(G))≤cfc(Lk(G)), with only the exception that G is isomorphic to a star of order at least 5 and $$k=1$$k=1. Finally, we obtain the exact values of $$cfc(L^k(G))$$cfc(Lk(G)), and use them as an efficient tool to get the smallest nonnegative integer $$k_0$$k0 such that $$cfc(L^{k_0}(G))=2$$cfc(Lk0(G))=2.

We study the problem of transforming one (vertex) k-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a k-coloring, where k denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant $$k \ge 4$$k≥4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if the number of colors is a fixed constant. We then demonstrate that, even when the number of colors is a part of input, the problem is solvable in polynomial time for several graph classes, such as split graphs and trivially perfect graphs.

This paper concerns the problem of scheduling jobs with unit processing time and nonidentical sizes on single or parallel identical batch machines. The objective is to minimize the total completion time of all jobs. We show that the worst-case ratio of the algorithm based on the bin-packing algorithm First Fit Increasing (FFI) lies in the interval $$[\frac{109}{82}, \frac{2+\sqrt{2}}{2}]\approx [1.3293, 1.7071]$$[10982,2+22]≈[1.3293,1.7071] for the single machine case, and is no more than $$\frac{6+\sqrt{2}}{4}\approx 1.8536$$6+24≈1.8536 for the parallel machines case.

We study the computational complexity of Power Edge Set (PES), for restricted graph classes with degree bounded by three (bipartite graph, Unit disk graphs and Grid graphs). This problem is devoted to the monitoring of an electric network. The aim is to minimize the number of edge-allocated PMUs in a network such that all vertices are monitored according to two spreading rules. We improve known complexity results using an L-reduction. We also derive some lowers bounds according to classic complexity hypothesis ($$\mathcal {P} \ne \mathcal {NP}$$P≠NP, $$\mathcal {UGC}$$UGC, $$\mathcal {ETH}$$ETH).

We continue the investigation proposed in [COCOA 2016, Weller, Chateau, Giroudeau, König and Pollet “On Residual Approximation in Solution Extension Problems”] about the study of extended problems. In this context, a partial feasible solution is given in advance and the goal is to extend this partial solution. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted complete graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results.

We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible: it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in $$O(n+m')$$O(n+m′) time, where $$m'$$m′ is the number of edges in the completed graph. This matches the complexity of the algorithm in [24] and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to $$O(n+m\log ^2 n)$$O(n+mlog2n) when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only O(n) edges, require $$\varOmega (n^2)$$Ω(n2) edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as $$O(n/\log ^2 n)$$O(n/log2n).

In the first part of our study, we extend the theory of basilica canonical decomposition by introducing new concepts known as towers and tower-sequences. The basilica canonical decomposition is a recently proposed tool in matching theory that can be applied non-trivially even for general graphs with perfect matchings. When studying matchings, the structure of alternating paths frequently needs to be considered. We show how a graph is made up of towers and tower-sequences, and thus obtain the structure of alternating paths in terms of the basilica canonical decomposition. This result provides a strong tool for analyzing general graphs with perfect matchings.The second part of our study is a new graph theoretic proof of the so-called Tight Cut Lemma derived from the first part of our study. To derive a characterization of the perfect matchings polytope, Edmonds, Lovász, and Pulleyblank introduced the Tight Cut Lemma as the most challenging aspect of their work. The Tight Cut Lemma in fact claims bricks as the fundamental building blocks that constitute a graph and can be referred to as a key result in this field. Although the Tight Cut Lemma itself is a purely graph theoretic statement, there was no known graph theoretic proof for decades until Szigeti provided such a proof using Frank-Szigeti’s optimal ear decomposition theory.By contrast, we provide a new proof using the extended theory of basilica canonical decomposition as the only preliminary result, and accordingly proposes a new strategy for studying bricks and tight cuts or matching theory in general. Our proof shows how the discussions on alternating paths construct the Tight Cut Lemma from first principles via the basilica canonical decomposition, even without using barriers, that is, the dual notion of matchings. The distinguishing features of our proof are that it is purely graph theoretic, purely matching (cardinality 1-matching) theoretic, and purely “primal” with respect to matchings.

Given a positive integer k and a directed graph G with a real number cost on each edge, the k-length negative cost cycle (kLNCC) problem that first emerged in deadlock avoidance in synchronized streaming computing network [14] is to determine whether G contains a negative cost cycle of at least k edges. The paper first shows a related problem of kLNCC, namely the fixed-point trail with k-length negative cost cycle (FPTkLNCC) problem which is to determine whether there exists a negative closed trail enrouting a given vertex as the fixed point and containing only cycles with at least k edges, is $$\mathcal{NP}$$NP-complete in multigraphs even when $$k=3$$k=3 by reducing from the 3SAT problem. Then as the main result, we prove the $$\mathcal{NP}$$NP-completeness of kLNCC by giving a more sophisticated reduction from the 3 Occurrence 3-Satisfiability (3O3SAT) problem, a known $$\mathcal{NP}$$NP-complete special case of 3SAT in which a variable occurs at most three times. The complexity result is surprising, since polynomial time algorithms are known for both 2LNCC (essentially no restriction on the value of k) and the k-cycle problem with k being fixed which is to determine whether there exists a cycle of at least length k in a given graph. This closes the open problem proposed by Li et al. in [14, 15] whether kLNCC admits polynomial-time algorithms.

Given a database instance d, a self join free conjunctive query q and its result q(d), contingency set $$\mathsf {\Gamma }(q,d)$$Γ(q,d) is a set of tuples from d such that $$q(d\setminus \mathsf {\Gamma })$$q(d\Γ) is false but q(d) is true initially. Finding minimum contingency set $$\mathsf {\Gamma }_{\min }(q,d)$$Γmin(q,d) is an important problem in database area. An important dichotomy for this problem was identified in the most recent result, Freire et al. showed that $${\mathsf \Gamma }_\textsf {min}(q_\triangle ,d)$$Γmin(q▵,d) is $$\mathsf {NP}$$NP-$$\mathsf {complete}$$complete if the input query includes a triad of form “$$R_{xy},S_{yz},T_{zx}$$Rxy,Syz,Tzx” in a particular manner, $$\mathsf {PTime}$$PTime otherwise. However, we have two observations: (a) if two clauses have a common variable, then this database instance should be too complex, formally speaking, the visualization of its query result will not be of planarity, this requirement is too strict, (b) there is no limitation on the length of every circle in the visualization of the query result. This makes the previous theorem of dichotomy too weak. Therefore, the natural question is that, if the query result of input database is not of planarity or there is a fixed limitation on the length of every circle, is it $${\mathsf \Gamma }_\textsf {min}(q_\triangle ,d)$$Γmin(q▵,d) still $$\mathsf {NP}$$NP-$$\mathsf {complete}$$complete? To this end, we strengthen the hardness result, that $${\mathsf \Gamma }_\textsf {min}(q_\triangle ,d)$$Γmin(q▵,d) is still $$\mathsf {NP}$$NP-$$\mathsf {complete}$$complete, if the input database instance is of planarity, or the maximum length of every circle is limited. Our theorems also generalize the result of triangle edge deletion problem defined on general graph into directed graph, make a contribution to graph theory.

In this paper, we introduce the notion of l-quasi-pyramidal and l-pseudo-pyramidal tours extending the classic notion of pyramidal tours to the case of the Generalized Traveling Salesman Problem (GTSP). We show that, for the instance of GTSP on n cities and k clusters with arbitrary weights, l-quasi-pyramidal and l-pseudo-pyramidal optimal tours can be found in time $$O(4^ln^3)$$O(4ln3) and $$O(2^lk^{l+4}n^3)$$O(2lkl+4n3), respectively. Consequently, we show that, in the most general setting, GTSP belongs to FPT for parametrizations induced by these special kinds of tours. Also, we describe a non-trivial polynomially solvable subclass of GTSP, for which the existence of l-quasi-pyramidal optimal tour (for some fixed value of l) is proved.

This paper studies the problem of locating two vertices in a cactus with positive and negative vertex weights. The problem has objective to minimize the sum of minimum weighted distances from every vertex of the cactus to the two medians. We develop an $$O(n^2)$$O(n2) algorithm for the 2-median problem, where n is the number of vertices of the cactus.

This paper is devoted to the ongoing study on the equilibrium points of AND-OR trees. Liu and Tanaka (2007, 2007a) characterized the eigen-distributions that achieve the distributional complexity, and among others, they proved the uniqueness of eigen-distribution for a uniform binary tree. Later, Suzuki and Nakamura (2012) showed that the uniqueness fails if only directional algorithms are allowed. Peng et al. (2016) extended the studies on eigen-distributions to balanced multi-branching trees of height 2. But, it remains open whether the uniqueness still holds or not for general multi-branching trees. To this end, we introduce the weighted trees, namely, trees with weighted cost depending on the value of a leaf. Using such models, we prove that for balanced multi-branching trees, the uniqueness of eigen-distribution holds w.r.t. all deterministic algorithms, but fails w.r.t. only directional algorithms.

In this paper, we study the maximum directed cut (MaxDC) problem. In the MaxDC, we are given a directed graph with nonnegative edge weights. Our goal is to obtain a bipartition of the vertices such that the total edge weight of the directed cut is maximized. By exploring the combinatorial characteristics of the optimal solution, we offer a 0.272-approximation algorithm based on the technique of spectral partitioning rounding.

We investigate the single vehicle scheduling problems based on tree/cycle networks. Each customer, assumed as a vertex on the given network, has a release time and a service time requirements. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the relatively optimal routing schedule so as to minimize the makespan. We provide a $$\frac{16}{9}$$169-approximation algorithm and a $$\frac{48}{25}$$4825-approximation algorithm for the tour-version and the path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version of single vehicle scheduling problem on a cycle, we present a $$\frac{5}{3}$$53-approximation algorithm.

We consider a general class of combinatorial optimization problems including among others allocation, multiple knapsack, matching or travelling salesman problems. The standard version of those problems is the maximum weight optimization problem where a sum of values is optimized. However, the sum is not a good aggregation function when the fairness of the distribution of those values (corresponding for example to different agents’ utilities or criteria) is important. In this paper, using the Generalized Gini Index (GGI), a well-known inequality measure, instead of the sum to model fairness, we formulate a new general problem, that we call fair combinatorial optimization. Although GGI is a non-linear aggregating function, a 0, 1-linear program (IP) can be formulated for finding a GGI-optimal solution by exploiting a linearization of GGI proposed by Ogryczak and Sliwinski [21]. However, the time spent by commercial solvers (e.g., CPLEX, Gurobi...) for solving (IP) increases very quickly with instances’ size and can reach hours even for relatively small-sized ones. As a faster alternative, we propose a heuristic for solving (IP) based on a primal-dual approach using Lagrangian decomposition. We demonstrate the efficiency of our method by evaluating it against the exact solution of (IP) by CPLEX on several fair optimization problems related to matching. The numerical results show that our method outputs in a very short time efficient solutions giving lower bounds that CPLEX may take several orders of magnitude longer to obtain. Moreover, for instances for which we know the optimal value, these solutions are quasi-optimal with optimality gap less than 0.3%.

Given a set of trips in a road network, where each trip has a vehicle, an individual and other requirements, the ridesharing problem is to deliver all individuals to their destinations by a subset of vehicles satisfying the requirements. Minimizing the total travel distance of the vehicles and minimizing the number of vehicles are major optimization goals. These minimization problems are complex and NP-hard because each trip may have many requirements. We study simplified minimization problems in which each trip’s requirements are specified by the source, destination, vehicle capacity, detour distance and preferred path parameters. We show that both minimization problems can be solved in polynomial time if all of the following conditions are satisfied: (1) all trips have the same destination; (2) no detour is allowed and (3) each trip has one unique preferred path. It is known that both minimization problems are NP-hard if any one of the three conditions is not satisfied. Our results and the NP-hard results suggest a clear boundary between the polynomial time solvable cases and NP-hard cases for the minimization problems.

The selfish bin packing problem (SBP) considers the classical bin packing problem in a game-theoretic setting where each item is controlled by a selfish agent. It is well-known that the classical bin packing problem admits an asymptotic fully polynomial-time approximation scheme (AFPTAS). However, all previously-studied cost-sharing mechanisms for the selfish bin packing problem (SBP) have PoA greater than 1.6. Obviously, there is quite a big gap between the results of the two highly-related problems. In this paper, we revisit the SBP and find more efficient mechanisms for SBP to narrow the gap. We first present a simple mechanism with $$PoA=1.5$$PoA=1.5, which significantly improves previous bounds. We observe that for a large class of mechanisms for the SBP, 1.5 is actually a lower bound of PoA. Finally, we propose new rules for the SBP which lead a better mechanism with $$PoA \le 1.467$$PoA≤1.467.

The theater defense distribution is an important problem in the military that determines strategies against a sequence of offensive attacks in order to protect his targets. This study focuses on developing mathematical models for two defense problems that generate anti-aircraft mission plans for a group of missile battalions. While the Anti-aircraft Mission Planning problem maximizes the defender’s effectiveness using all his available battalions, the Inverse Anti-aircraft Mission Planning problem computes necessary weapon resources (battalions and their missiles) to obtain a given defensive effectiveness value. The proposed formulations are Mixed Integer Programs that describe not only the positions of missile battalions, but also engage battalions to fleets of attacking aircrafts. We additionally prove that these problems are NP-hard. A comprehensive set of experiments is then evaluated to show that these proposed programs can be applied to solve fast real-life instances to optimality.

Urban railway system is of great importance to public transportation and economic development. However, due to the fast development of urban cities and time-consuming construction, it is quite challenging to plan a successful metro railway system beforehand. In this paper, we propose perspectives of evaluating traffic efficiency of metro railway systems from various factors such as the total railway traffic flow, the structure of the traffic system and the spatial distribution of work-and-home. We evaluate the implementation effect of Shenzhen railway system (particular the second phase construction) based on historical and real-time data reported by 28,000 passengers, which will provide insightful suggestions for Shenzhen metro construction in the future.

In order to simulate the self-replication of computer bacteria, a new model named cloning automata is put forward. It can simulate the self-replication in two different ways: fusion and fission. Properties such as the self-replicating velocity and the threshold time for denial of service are analyzed. Also, methods for interrupting the self-replicating behavior are presented. As an example, a concrete computer bacterium i.e. fork bomb is simulated and analyzed with cloning automata.

In this paper, a Point Merge arrival integration method of tactical operation is introduced under current Communication, Navigation and Surveillance technologies. In present research, the multi-agent theory is used to build and stimulate the arrival integration system. Agents involved in point merge operation and action modules are designed to realize automatic trajectory generating, adjustment, sequencing and conflict detection. The architecture of point merge operation is obtained as well. In order to verify the method, historical ADS-B data is analyzed and the point merge procedures are designed for single runway and two runway arrival separately for different verification. The outcome proves the correctness and efficiency of the method and demonstrates the advantage of Point merge procedure on reducing flight time, fuel consumption, delay time and ATC workload.

Inconsistent data indicates that there is conflicted information in the data, which can be formalized as the violations of given semantic constraints. To improve data quality, repair means to make the data consistent by modifying the original data. Using the feedbacks of users to direct the repair operations is a popular solution. Under the setting of big data, it is unrealistic to let users give their feedbacks on the whole data set. In this paper, the repair position selection problem (RPS for short) is formally defined and studied. Intuitively, the RPS problem tries to find an optimal set of repair positions under the limitation of repairing cost such that we can obtain consistent data as many as possible. First, the RPS problem is formalized. Then, by considering three different repair strategies, the complexities and approximabilities of the corresponding RPS problems are studied.

One-way trading is a fundamental problem in the online algorithms. A seller has some product to be sold to a sequence of buyers $$\{u_1, u_2, \dots \}$${u1,u2,⋯} in an online fashion and each buyer $$u_i$$ui is associated with his accepted unit price $$p_i$$pi, which is known to the seller on the arrival of $$u_i$$ui. The seller needs to decide the amount of products to be sold to $$u_i$$ui at the then-prevailing price $$p_i$$pi. The objective is to maximize the total revenue of the seller. In this paper, we study the unbounded one-way trading, i.e., the highest unit price among all buyers is unbounded. We also assume that the highest prices of buyers follow some distribution with monotone hazard rate, which is well-adopted in Economics. We investigate two variants, (1) the distribution is on the highest price among all buyers, and (2) a general variant that the prices of buyers is independent and identically distributed. To measure the performance of the algorithms, the expected competitive ratios, $$\mathrm {E}[OPT]/\mathrm {E}[ALG]$$E[OPT]/E[ALG] and $$\mathrm {E}[OPT/ALG]$$E[OPT/ALG], are considered and constant-competitive algorithms are given if the distributions satisfy the monotone hazard rate.

The flash memories have gained considerable attention to replace hard-disk drives in modern storage applications because of the following excellent features such as the low cost, low power consumption, and high storage densities as compared to other non-volatile technologies. However, some error types are associated with flash memories such as charge leakage and inter-cell interference errors. It leads to the bidirectional limited magnitude channel model if both the error types are considered together. It has been observed that these error types are data value dependent for 2-bit MLC flash; they have different probabilities to become erroneous. In this paper, we consider the bidirectional limited magnitude errors by considering the data value dependencies of these error sources. A code construction to correct bidirectional limited magnitude errors is provided as well. The proposed code construction is the generalized case of asymmetric, symmetric, and bidirectional limited magnitude error correcting codes.

To satisfy the increasing demand for various types of coastal wireless communication, the pursuit of fully functional and low cost means of maritime broadband communication is imminent. High Altitude Platform (HAP) based maritime communication is a promising solution to improve the quality of coverage on the sea. In this paper, we present Integrated HAP-Sea-Land Network (IHSL) architecture for maritime broadband communication. And then we focus on the problem of Optimal Topology Design (OTD) which is an important issue for the IHSL network deployment in practice. We formulate the OTD problem as a generic integer linear programming (ILP) model with the objective of minimizing the total deployment cost subject to coverage, reliability, and topology constraints of the network. The linear programming solver Gurobi is applied to solve the ILP model. A series of case studies are conducted to validate the optimization framework and demonstrated the solvability and scalability of the ILP model. The simulation results show the significant performance benefits of IHSL in terms of cost and reliability under 1-coverage and 2-coverage. The proposed optimization framework is expected to provide a guideline for the IHSL network deployment in practice.

In this paper, we look into the problem of storing a subset $$\mathcal {S}$$S containing at most two elements of the universe $$\mathcal {U}$$U in the adaptive bitprobe model. Due to the work of Radhakrishnan et al. [3], and more recently of Lewenstein et al. [2], we have excellent schemes for storing such an $$\mathcal {S}$$S, and answering membership queries using two or more bitprobes. Yet, Nicholson et al. [4] in their survey of the area noted that the space lower bound of even the first non-trivial scenario, namely that of answering membership of $$\mathcal {S}$$S using two bitprobes, is still open. Towards that end, we propose an unified geometric approach to designing schemes in this domain. If t is the number of bitprobes allowed, we arrange the universe $$\mathcal {U}$$U in a $$(2t-1)$$(2t-1)-dimensional hypercube, and look at its two-dimensional faces. This approach matches the space bound of the best known schemes for certain cases, and gives results that are close to the best known schemes for others.