Approximation algorithms for the maximally balanced connected graph tripartition problem

Journal of Combinatorial Optimization - Given a vertex-weighted connected graph $$G = (V, E, w(\cdot ))$$ , the maximally balanced connected graph k-partition (k-BGP) seeks to partition the vertex...     

Approximation algorithms for two variants of correlation clustering problem

Correlation clustering problem is a clustering problem which has many applications such as protein interaction networks, cross-lingual link detection, communication networks, and social computing. In this paper, we introduce two variants of correlation clustering problem: correlation clustering problem on uncertain graphs and correlation clustering problem with non-uniform hard constrained cluster sizes. Both problems overcome part of the limitations of the existing variants of correlation clustering problem and have practical applications in the real world. We provide a constant approximation algorithm and two approximation algorithms for the former and the latter problem, respectively.

     

Approximation algorithms for minimum weight partial connected set cover problem

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set \(U\), an integer \(q\le |U|\), a collection \(\mathcal {E}\) of subsets of \(U\), and a connected graph \(G_{\mathcal {E}}\) on vertex set \(\mathcal {E}\), the goal is to find a minimum weight subcollection of \(\mathcal {E}\) which covers at least \(q\) elements of \(U\) and induces a connected subgraph in \(G_{\mathcal {E}}\). In this paper, we derive a “partial cover property” for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are adjacent in \(G_{\mathcal {E}}\) (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio \(\rho (1+H(\gamma ))+o(1)\), and (b) for the cardinality version under the assumption that any pair of sets in \(\mathcal {E}\) with nonempty intersection are at most \(d\)-hops away from each other (the Minimum Partial Connected \(k\)-Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio \(2(1+dH(\gamma ))+o(1)\), where \(\gamma =\max \{|X|:X\in \mathcal {E}\}\), \(H(\cdot )\) is the Harmonic number, and \(\rho \) is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

Priority algorithms for the subset-sum problem

Greedy algorithms are simple, but their relative power is not well understood. The priority framework (Borodin et al. in Algorithmica 37:295–326, 2003) captures a key notion of “greediness” in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions, for which the accepted data items can be later rejected to maintain the feasibility of the solution. We first provide a tight bound of α≈0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β≈0.780 and γ≈0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ≈0.893. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS 4598, pp. 504–514.     

The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

Approximation algorithms for pricing with negative network externalities

We study the problems of pricing an indivisible product to consumers who are embedded in a given social network. The goal is to maximize the revenue of the seller by the so-called iterative pricing that offers consumers a sequence of prices over time. The consumers are assumed to be impatient in that they buy the product as soon as the seller posts a price not greater than their valuations of the product. The product’s value for a consumer is determined by two factors: a fixed consumer-specified intrinsic value and a variable externality that is exerted from the consumer’s neighbors in a linear way. We focus on the scenario of negative externalities, which captures many interesting situations, but is much less understood in comparison with its positive externality counterpart. Assuming complete information about the network, consumers’ intrinsic values, and the negative externalities, we prove that it is NP-hard to find an optimal iterative pricing, even for unweighted tree networks with uniform intrinsic values. Complementary to the hardness result, we design a 2-approximation algorithm for general weighted networks with (possibly) nonuniform intrinsic values. We show that, as an approximation to optimal iterative pricing, single pricing works fairly well for many interesting cases, such as forests, Erd?s–Rényi networks and Barabási–Albert networks, although its worst-case performance can be arbitrarily bad in general networks.     

Combinatorial algorithms for the maximum k-plex problem

The maximum clique problem provides a classic framework for detecting cohesive subgraphs. However, this approach can fail to detect much of the cohesive structure in a graph. To address this issue, Seidman and Foster introduced k-plexes as a degree-based clique relaxation. More recently, Balasundaram et al. formulated the maximum k-plex problem as an integer program and designed a branch-and-cut algorithm. This paper derives a new upper bound on the cardinality of k-plexes and adapts combinatorial clique algorithms to find maximum k-plexes.     

Target-guided algorithms for the container pre-marshalling problem

The container pre-marshalling problem (CPMP) aims to rearrange containers in a bay with the least movement effort; thus, in the final layout, containers are piled according to a predetermined order. Previous researchers, without exception, assumed that all the stacks in a bay are functionally identical. Such a classical problem setting is reexamined in this paper. Moreover, a new problem, the CPMP with a dummy stack (CPMPDS) is proposed. At terminals with transfer lanes, a bay includes a row of ordinary stacks and a dummy stack. The dummy stack is actually the bay space that is reserved for trucks. Therefore, containers can be shipped out from the bay. During the pre-marshalling process, the dummy stack temporarily stores containers as an ordinary stack. However, the dummy stack must be emptied at the end of pre-marshalling. In this paper, target-guided algorithms are proposed to handle both the classical CPMP and new CPMPDS. All the proposed algorithms guarantee termination. Experimental results in terms of the CPMP show that the proposed algorithms surpass the state-of-the-art algorithm.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Optimal algorithms for uncovering synteny problem

The syntenic distance between two genomes is the minimum number of fusions, fissions, and translocations that can transform one genome to the other, ignoring the gene order within chromosomes. As the problem is NP-hard in general, some particular classes of synteny instances, such as linear synteny, exact synteny and nested synteny, are examined in the literature. In this paper, we propose a new special class of synteny instances, called uncovering synteny. We first present a polynomial time algorithm to solve the connected case of uncovering synteny optimally. By performing only intra-component moves, we then solve the unconnected case of uncovering synteny. We will further calculate the diameters of connected and unconnected uncovering synteny, respectively.     

Robust,multi-objective optimization for the military medical evacuation location-allocation problem

Determining where to locate mobile aeromedical staging facilities (MASFs) as well as identifying how many aeromedical helicopters to allocate to each MASF, commonly referred to as the medical evacuation (MEDEVAC) location-allocation problem, is vital to the success of a deployed MEDEVAC system. Within this research, we develop an integer mathematical programming formulation to determine the location and allocation of MEDEVAC assets over the phases of a military deployment to support operations ranging from peacekeeping through combat to post-combat resolution. Our model seeks to address the multi-objective problem of maximizing the expected demand coverage as a measure of solution effectiveness, minimizing the maximum number of located MASFs in any deployment phase as a measure of solution efficiency, and minimizing the total number of MASF relocations throughout the deployment as a measure of solution robustness. This research makes two contributions. First, it formulates a representative mathematical programming formulation and identifies an accompanying solution methodology (i.e., the ε-constraint Method) to assess and recommend improvements to deployed military MEDEVAC systems designed to provide large-scale emergency medical response for contingency operations that range in casualty-inducing intensity (i.e., demand) over the phases of a deployment. Second, the research illustrates the application of the model for a realistic, synthetically generated medical planning scenario in southern Azerbaijan. Comparisons are made between the model’s (multi-phase) optimal solution and the phase-specific optimal solutions that disregard concerns of transitions between phases. The results highlight the conflicting nature between the objectives and illustrate the trade-offs between objectives as restrictions applied to the second and third objectives are respectively tightened or relaxed.     

Approximation algorithms and hardness results for labeled connectivity problems

Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s – t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.     

Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

Greedy algorithms for the profit-aware social team formation problem

Motivated by applications in online labor markets, we study the problem of forming multiple teams of experts in a social network to accomplish multiple tasks that require different combinations of skills. Our goal is to maximize the total profit of tasks that are completed by these teams subject to the capacity constraints of the experts. We study both the offline and online settings of the problem. For the offline problem, we present a simple and practical algorithm that improves upon previous results in many situations. For the online problem, we design competitive deterministic and randomized online algorithms. These are complemented by some hardness results in both settings.

     

Exact and approximate algorithms for the loop layout problem

Control parameters, such as order frequency, safety stock and safety time, are important tools to improve the logistic performance in material planning. In practice, the adjustment of control parameters appears to be very difficult. One of the reasons is the lack of relevant tactical control information: a simple, periodical and per-commodity integrated feedback of performance and process information often is not available to the logistic operator. Therefore, the material planner is offered a fairly limited overview and insight of the processes to be controlled. This problem has been investigated in several plants in the Netherlands. A solution to this problem is first to measure the performance, the frequency of process disturbances and the effect of the parameters on performance for all commodities involved. And second, to integrate this information and provide feedback to the responsible material planner. In this article a design for decision support is presented to integrate and give feedback of relevant tactical control information. Prototype information systems are now being tested in practice and in the laboratory. The expectation is that this type of decision support will help the operator to make more systematic and effective diagnoses.     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

Polynomial-time approximation algorithms for the coloring problem in some cases

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.     

Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems

When ties and incomplete preference lists are permitted in the Stable Marriage and Hospitals/Residents problems, stable matchings can have different sizes. The problem of finding a maximum cardinality stable matching in this context is known to be NP-hard, even under very severe restrictions on the number, size and position of ties. In this paper, we describe polynomial-time 5/3-approximation algorithms for variants of these problems in which ties are on one side only and at the end of the preference lists. The particular variant is motivated by important applications in large scale centralised matching schemes. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 548–558. This work was supported by EPSRC grant EP/E011993/1.