Search

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]

Motivated by some applications in communication networks of the diameter-constrained minimum spanning tree (Diamc-MST) problem, we address the delay-constrained minimum shortest path tree (Delayc-MSPT) problem, which is a variation of the Diamc-MST problem. Specifically, given a weighted graph G = (V , E ; w , c) and a constant d 0 , where n = | V | , m = | E | , length function w : E → R + and cost function c : E → R + , we are asked to determine a minimum shortest path tree among all shortest path trees (in G) whose delays are no more than d 0 , where the delay of a shortest path tree is the maximum distance (with respect to w (⋅)) from its source to every other leaf in that tree, and the cost of such a shortest path tree is the sum of costs of all edges (with respect to c (⋅)) in that tree. In addition, when a constant d 0 is the radius of G , we refer to this version of the Delayc-MSPT problem as the minimum radius minimum shortest path tree (MinRadius-MSPT) problem, and when a constant d 0 is the diameter of G , we refer to that version of the Delayc-MSPT problem as the maximum delay minimum shortest path tree (MaxDelay-MSPT) problem. In addition, we consider the diameter-constrained minimum shortest path tree (Diamc-MSPT) problem, except substituting the diameter for the delay of G in the Delayc-MSPT problem, where the diameter of a shortest path tree is the maximum distance (with respect to w (⋅)) between any two leaves in that tree. The main contribution of our paper is to show the following results. (1) We design an exact algorithm to solve the Delayc-MSPT problem and a similar exact algorithm to solve the MinRadius-MSPT problem, respectively, and these two algorithms run in time O (n 3) ; (2) We present an exact algorithm to solve the MaxDelay-MSPT problem, and that algorithm runs in time O (n 3) ; (3) We provide an exact algorithm to solve the special version of the Diamc-MSPT problem, where the constant d 0 is exactly the diameter of G , and that algorithm runs in time O (m n 2 + n 3 log ⁡ n). • We study the delay-constrained minimum shortest path tree problem and related problems. • The goal is to find a minimum shortest path tree whose delay is no more than d. • We design a polynomial-time algorithm to solve our problem. • we provide other polynomial-time algorithms to solve related problems. [ABSTRACT FROM AUTHOR]

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V , w) with vertex set V consisting of two parts D (containing depots) and V ∖ D (containing nodes), and a budget B ≥ 0 , the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V ∖ D , satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (log ⁡ B μ) -approximation algorithm, where μ is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log ⁡ n) -approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. • A log-factor approximation algorithm for the single depot budgeted cycle cover problem. • A log-factor approximation algorithm for the multi-depot budgeted cycle cover problem. • Experiments on randomly generated instances show good performance of the algorithms. [ABSTRACT FROM AUTHOR]

The Stop Number Problem arises in the management of a dial-a-ride system served by a fleet of autonomous electric vehicles. In such a system, clients request for a ride from an origin station to a destination station, and a fleet of capacitated vehicles must satisfy all requests. The goal is to minimize the number of pick-up/drop-off operations. In this paper we focus on a constrained unitary variant, called Unit Stop Number Problem, where each client requests for a single seat in the vehicles. This variant was recently conjectured to be NP-Hard. In this regard, we show how this problem relates to other problems known in the literature in order to derive some polynomial-time solvable variants. Moreover, we provide a positive answer to the conjecture by showing that the problem is NP-Hard for any fixed capacity greater than or equal to 2, even for the case where the graph of requests is restricted to the class of planar bipartite graphs. Our proof of NP-Hardness also improves the complexity results known in the literature for the related problems identified. [ABSTRACT FROM AUTHOR]

k -Clustering partitions a set of n points in a metric space into at most k clusters in a way that makes the resulted clusters satisfy both the homogeneity and the separation criteria. The diameter of a cluster is the maximum distance between pairs of points in the cluster, and the split of a cluster is the minimum distance between points of the cluster and ones outside the cluster. In this paper, we propose a new criterion for measuring the goodness of clusters: The ratio of the minimum cluster split to the maximum cluster diameter (abbr. RSD). We study the following two optimization problems: Maximizing RSD without and with cardinality constraints, i.e., each cluster should consist of at least N points. For both problems with k ≥ 3 , it is NP-hard to achieve a factor of (1 2 + ϵ) approximation for any ϵ > 0. For k = 2 , we solve the two problems optimally; For k ≥ 3 , we present a 1 2 -approximation and a 1 4 -approximation algorithm for the two problems, respectively. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems is discussed. It is assumed that a solution can be constructed in two stages. The current first-stage costs are precisely known, while the future second-stage costs are only known to belong to an uncertainty set, which contains a finite number of scenarios with known probability distribution. A partial solution, chosen in the first stage, can be completed by performing an optimal recourse action, after the true second-stage scenario is revealed. A solution minimizing the Conditional Value at Risk (CVaR) measure is computed. Since expectation and maximum are boundary cases of CVaR, the model generalizes the traditional stochastic and robust two-stage approaches, previously discussed in the existing literature. In this paper some new negative and positive results are provided for basic combinatorial optimization problems such as the selection or network problems. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop (1 , 2)-Minimum Spanning Tree problem (abbr. 2H-(1 , 2)-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-(1 , 2)-MSTP (including the (1 + 1) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the (1 + 1) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones. [ABSTRACT FROM AUTHOR]

Rough set theory is a granular computing tool used to deal with ambiguity and uncertainty in information systems. However, many optimization problems in rough sets, such as attribute reduction, are NP-hard problems, and most of the algorithms for these problems are greedy. As a complex mathematical structure, matroids provide a powerful tool for solving combinatorial optimization problems related to attribute reduction. Therefore, it is necessary to study the combination of matroids and rough sets. This paper uses rough sets and matrix approaches to spanning matroids. Moreover, the features of spanning matroids are applied to attribute reduction in decision information systems. Firstly, we construct spanning sets based on equivalence relations which can induce matroids called spanning matroids. Secondly, some features of spanning matroids, such as closed sets, bases, are studied by matrix method. Finally, the judgment theorems with the features of spanning matroids are proposed for addressing the problems about attribute reduction in decision information systems. Simultaneously, the sufficient and necessary conditions for distinguishing upper approximation reduction in inconsistent decision information systems are obtained from the viewpoint of spanning matroids. [ABSTRACT FROM AUTHOR]

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l 1 norm, weighted l 2 norm, weighted l ∞ norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. Strongly polynomial algorithms are presented for the models we studied. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of selfish bin packing with punishment. Different from the selfish bin packing problem proposed by Bilò in 2006, where the items are astute to minimize their shared proportional cost in a bin, we consider the case that items are into the utility defined as the load of bin it is packed in and, a unilateral moving may incur punishment. We define and consider several kinds of punishment, which can be roughly classified into two types: the punishment according to the behavior and the punishment based on the result. For both types we present the tight bound for Price of Anarchy (PoA) under the objective of minimizing the number of bins used. The results proved show that punishment does not always work, a punishment based on the result can be viewed as a delicate designed threat in advance which could perform much better, with an approximate 1.48 upper bound comparing to the optimal solution. • Initiate the consideration of punishment into the bin packing game. • Define three versions of punishment for the selfish bin packing problem. • Prove that punishment may not help to get better performance ratio. • Propose a dissuasive mechanism which could encourage agents to form a better equilibrium profile. [ABSTRACT FROM AUTHOR]

The grounded Laplacian matrix L − S of a graph G = (V , E) with n = | V | nodes and m = | E | edges is a (n − s) × (n − s) submatrix of its Laplacian matrix L , obtained from L by deleting rows and columns corresponding to s = | S | ≪ n ground nodes forming set S ⊂ V. The smallest eigenvalue of L − S plays an important role in various practical scenarios, such as characterizing the convergence rate of leader-follower opinion dynamics, with a larger eigenvalue indicating faster convergence of opinion. In this paper, we study the problem of adding k ≪ n edges among all the nonexistent edges forming the candidate edge set Q = (V × V) ﹨ E , in order to maximize the smallest eigenvalue of the grounded Laplacian matrix. We show that the objective function of the combinatorial optimization problem is monotone but non-submodular. To solve the problem, we first simplify the problem by restricting the candidate edge set Q to be (S × (V ﹨ S)) ﹨ E , and prove that it has the same optimal solution as the original problem, although the size of set Q is reduced from O (n 2) to O (n). Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio (1 − e − α γ) / α and time complexity O (k n 4) , where γ and α are, respectively, submodularity ratio and curvature, whose bounds are provided for some particular cases. The other is a fast greedy algorithm without approximation guarantee, which has a running time O ˜ (k m) , where O ˜ (⋅) suppresses the poly (log ⁡ n) factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

• A bicriteria approximation algorithm for Max k -Uncut with ratio at least 1/2. • A bicriteria approximation algorithm for Densest k -Subgraph with ratio at least 1/4. • A new perspective to the Densest k -Subgraph problem. The Max k -Uncut problem arose from the study of homophily of large-scale networks. Given an n -vertex undirected graph G = (V , E) with nonnegative weights defined on edges and a positive integer k , the Max k -Uncut problem asks to find a partition { V 1 , V 2 , ⋯ , V k } of V such that the total weight of edges that are not cut is maximized. This problem is the complement of the classic Min k -Cut problem, and was proved to have surprisingly rich connection to the Densest k -Subgraph problem. In this paper, we give an approximation algorithm for Max k -Uncut using a non-uniform approach combining LP-rounding and the greedy strategy. The algorithm partitions the vertices of G into at least (1 − 1 e) k parts in expectation, and achieves a good expected approximation ratio 1 2 (1 + (n − k n) 2). [ABSTRACT FROM AUTHOR]

We propose a dynamic programming framework for an exact multi-stage (lexicographic) combinatorial optimization. Unlike conventional algorithms of dynamic programming that return one optimal solution, two dynamic programming algorithms proposed in this paper are coping with the whole set of optimal solutions or with its essential part. We describe the set of elements for optimization by a labeled directed acyclic graph, which in some sense, is similar to the structure of subproblems of the considered problem. For a given cost function (objective), the first algorithm constructs a subgraph of this graph that describes the whole set of optimal elements or its essential part. This algorithm can be used for multi-stage optimization of elements relative to a sequence of cost functions. The second algorithm counts elements before the optimization and after each optimization step. The considered labeled directed acyclic graph is a kind of circuit. This circuit builds the set of elements for optimization from one-element sets attached to input nodes. It uses the operation of union of sets attached to unifying nodes and functional operations attached to functional nodes. The algorithms for optimization and counting elements are defined for an arbitrary circuit without repetitions in which each element is generated exactly one time. For a considered problem with a known conventional dynamic programming solution algorithm, usually, it is easy to construct a corresponding circuit without repetitions. Once the circuit and cost functions are defined, our framework provides the correctness proofs and detailed time complexity analysis for the proposed algorithms. To make this approach more intuitive, we consider an illustrative example related to the maximum subarray problem. We tested our approach on the following nine combinatorial optimization problems: matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, optimal bitonic tour, segmented least squares, convex polygon triangulation, one-dimensional clustering, and line breaking (text justification). We consider the last three problems in detail: construct a circuit without repetitions, describe at least two cost functions, evaluate a number of operations and time required by the algorithms, discuss an example, and consider the results of computer experiments with randomly generated instances of the problem. [ABSTRACT FROM AUTHOR]

We study the combinatorial FIFO Stack-Up problem. In the delivery industry, bins have to be moved from conveyor belts onto pallets. Given is a list Q of k sequences of labeled bins and a positive integer p. The goal is to palletize the bins by iteratively removing the first bin of one of the k sequences and putting it onto a pallet located at one of p stack-up places. Each of these pallets has to contain bins of only one label, bins of different labels have to be placed on different pallets. After all bins of one label have been removed from the given sequences, the corresponding stack-up place becomes available for a pallet of bins of another label. The FIFO Stack-Up problem asks whether such a processing is possible. The FIFO Stack-Up problem is known to be NP-complete even if the sequences of Q contain together at most c Q = 6 bins per pallet. This implies that the problem is also hard if all bins of every pallet are distributed to at most d Q = 6 sequences. In this paper we strengthen the hardness to the cases c Q = 5 and d Q = 3. We also show the hardness for the practical case where the number of sequences is smaller than the number of pallets, and we point out differences to related problems like 3D Bin Packing and Train Marshalling. [ABSTRACT FROM AUTHOR]

The sheer size of modern datasets has led to an urgent need for summarization techniques that can identify representative elements of the data set. Fortunately, the vast majority of data summarization tasks satisfy an intuitive diminishing returns condition known as submodularity, which allows us to find nearly-optimal solutions in linear time. However, for many applications in practice, including experimental design and sparse Gaussian processes, the objective is in general not submodular. To solve these optimization problems, an important research method is to describe the characteristics of the non-submodular functions. The non-submodular function is a hot research topic in the study of nonlinear combinatorial optimizations. In this paper, we combine and generalize the curvature and the generic submodularity ratio to design an approximation algorithm for two-stage non-submodular maximization under a matroid constraint. [ABSTRACT FROM AUTHOR]

The knapsack problem (KP) is a very famous NP-hard problem in combinatorial optimization. Also its generalization to multiple dimensions named d-dimensional knapsack problem (d-KP) and to multiple knapsacks named multiple knapsack problem (MKP) are well known problems. In this paper we give a first study on the fixed-parameter tractability of these three problems. The idea behind fixed-parameter tractability is to split the complexity into two parts – one part that depends purely on the size of the input and one part that depends on some parameter of the problem that tends to be small in practice. Further we consider the closely related question, whether the sizes and the values can be reduced, such that their bit-length is bounded polynomially or even constantly in a given parameter, i.e. the existence of kernelizations is studied. We give several upper and some lower bounds on the parameterized complexity and kernel sizes for the following parameters: the number of items, the threshold value for the profit, the sizes, the profits, the number d of dimensions, and the number m of knapsacks. We also consider the connection of parameterized knapsack problems to linear programming, approximation, and pseudo-polynomial algorithms. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we consider an inverse obnoxious p -median location problem with p ≥ 2 on trees in which the aim is to change the edge lengths at the minimum total cost so that a predetermined set of p vertices becomes an obnoxious p -median location. A novel combinatorial algorithm with O (p 2 | V (T) | 2 log 2 ⁡ | V (T) |) time complexity is proposed for obtaining an optimal solution of the problem under the weighted Manhattan norm. Moreover, optimal solution algorithms with O (p 2 | V (T) |) time complexity are developed for the problem under the weighted Chebyshev norm and the weighted bottleneck-type Hamming distance. [ABSTRACT FROM AUTHOR]

Abstract Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered particle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable posterior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the difficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler's Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida's Random Energy Model (REM). Furthermore, the derived free energy asymptotics lead to a theoretical justification of a recently introduced concept [3] of Gibbs posterior agreement that measures stability of the Gibbs distributions when the cost function fluctuates due to randomness in the input. This relatively new stability concept may potentially provide a new method to select robust solutions for a large class of optimization problems. [ABSTRACT FROM AUTHOR]

Partitioning a network into k pieces is a fundamental problem in network science. A simple measure of partitioning a network is provided by the Max k -Uncut problem. Given an n -vertex undirected graph G with nonnegative weights defined on edges, and a positive integer k , the Max k -Uncut problem asks to find a k -partition of the vertices of G to maximize the total weight of edges that are not in the cut. This problem is the complement of the classic Min k -Cut problem, and has close relation to many combinatorial optimization problems, including the famous Densest k -Subgraph problem. In this paper, we propose a greedy approximation algorithm for the Max k -Uncut problem with performance ratio 1 − 2 (k − 1) n. The algorithm is very simple, which consists of only k − 1 min cut computations. The algorithm has fast running time O (k n 2) and is hence implementable. The experimental results show that the algorithm has excellent practical performance. [ABSTRACT FROM AUTHOR]

The Burrows–Wheeler Transform (BWT) is a reversible transformation on which are based several text compressors and many other tools used in Bioinformatics and Computational Biology. The BWT is not actually a compressor, but a transformation that performs a context-dependent permutation of the letters of the input text that often create runs of equal letters (clusters) longer than the ones in the original text, usually referred to as the “clustering effect” of BWT. In particular, from a combinatorial point of view, great attention has been given to the case in which the BWT produces the fewest number of clusters (cf. [5,16,21,23] ). In this paper we are concerned about the cases when the clustering effect of the BWT is not achieved. For this purpose we introduce a complexity measure that counts the number of equal-letter runs of a word. This measure highlights that there exist many words for which BWT gives an “un-clustering effect”, that is BWT produce a great number of short clusters. More in general we show that the application of BWT to any word at worst doubles the number of equal-letter runs. Moreover, we prove that this bound is tight by exhibiting some families of words where such upper bound is always reached. We also prove that for binary words the case in which the BWT produces the maximal number of clusters is related to the very well known Artin's conjecture on primitive roots. The study of some combinatorial properties underlying this transformation could be useful for improving indexing and compression strategies. [ABSTRACT FROM AUTHOR]

Cadences are syntactic regularities in strings, of the family of periods, squares, and repetitions. We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. Although cadences' combinatorial properties have been explored, little work was done regarding the efficiency of their discovery. Recently, implementations involving cadences appeared in works on phylogenetic reconstruction, periodic subgraph mining, and monitoring events in computer networks. In this paper we begin a systematic study of the efficiency of finding cadences. We first give some basic definitions; we then give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences; finally, we propose a data structure that captures many features of cadences and allows for the efficient detection of many types of cadences. In particular, all sub-cadences can be detected and reported in time proportional to the sum of their lengths. [ABSTRACT FROM AUTHOR]

Popular matchings have been intensively studied recently as a relaxed concept of stable matchings. By applying the concept of popular matchings to branchings in directed graphs, Kavitha et al. introduced popular branchings. Let G = (V G , E G) be a directed graph, where each vertex has preferences over its incoming arcs, and B and B ′ be branchings in G. A vertex v ∈ V G prefers B to B ′ if v prefers its incoming arc of B to that of B ′ , where having an arbitrary incoming arc is preferred to having no incoming arc. We say that B is more popular than B ′ if the number of vertices preferring B to B ′ is greater than the number of vertices preferring B to B ′. A branching B is called a popular branching if there is no branching more popular than B. Kavitha et al. proposed an algorithm for finding a popular branching when the preferences of each vertex are given by a strict partial order. The correctness of this algorithm is proved by utilizing classical theorems on the duality of weighted arborescences. In this paper, we generalize popular branchings to weighted popular branchings in vertex-weighted directed graphs, in the same manner as weighted popular matchings by Mestre. We give an algorithm for finding a weighted popular branching for the case where the preferences of each vertex are given by a total preorder and the weights satisfy certain conditions. Our algorithm is based on Kavitha et al.'s algorithm, while it includes elaborated procedures resulting from the vertex-weights. Its correctness also builds upon the duality of weighted arborescences. [ABSTRACT FROM AUTHOR]

Abstract: There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in time where is the number of creases and is the total crease width. [Copyright &y& Elsevier]

In this paper, we study several combinatorial optimization problems which combine the classic open shop or job shop scheduling problem and the shortest path problem. Our goal is to select a subset of jobs that constitutes a feasible solution of the shortest path problem, and then execute the selected jobs on the shop machines to minimize the makespan, i.e., the last completion time of all the jobs. We prove that these problems are NP-hard even if there are two machines. If the number of machines is an input, we show that it is unlikely to find approximation algorithms with performance ratios better than 2 unless P = NP . We present an intuitive approximation algorithm when the number of machines is an input, and an improved approximation algorithm when the number of machines is fixed. In addition, we propose a polynomial time approximation scheme for the open shop case when the number of machines is fixed. [ABSTRACT FROM AUTHOR]

This paper aims to study techniques for designing truthful mechanisms for a combinatorial optimization problem that might require composition algorithms. We show that the composition algorithm A ∘ B is monotone if the algorithm A and the algorithm B are both monotone. We apply this technique to the two-dimensional orthogonal knapsack problem with provable constant approximation bounds, improving the previous non-constant results in [5] . Moreover, we show that the technique can also be applied to the heterogeneous multiple clusters scheduling problem, and a truthful mechanism with provable approximation bounds was presented. [ABSTRACT FROM AUTHOR]

In Bujtás et al. (2011) [4] the authors introduced a very general problem called Graph-Bin Packing (GBP). It requires a mapping μ : V ( G ) → V ( H ) from the vertex set of an input graph G into a fixed host graph H , which, among other conditions, satisfies that for each pair u , v of adjacent vertices the distance of μ ( u ) and μ ( v ) in H is between two prescribed bounds. In this paper we propose two online versions of the Graph-Bin Packing problem. In both cases the vertices can arrive in an arbitrary order where each new vertex is adjacent to some of the previous ones. One version is a Maker–Breaker game whose rules are defined by the packing conditions. A subclass of Maker-win input graphs is what we call ‘well-packable’; it means that a packing of G is obtained whenever the mapping μ ( u ) is generated by selecting an arbitrary feasible vertex of the host graph for the next vertex of G in each step. The other model is connected-online packing where we are looking for an online algorithm which can always find a feasible packing. In both models we present some sufficient and some necessary conditions for packability. In the connected-online version we also give bounds on the size of used part of the host graph. [ABSTRACT FROM AUTHOR]

Abstract: The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002)  showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems. [Copyright &y& Elsevier]

Abstract: In this paper the minimum spanning tree problem with uncertain edge costs is discussed. In order to model the uncertainty a discrete scenario set is specified and a robust framework is adopted to choose a solution. The min–max, min–max regret and 2-stage min–max versions of the problem are discussed. The complexity and approximability of all these problems are explored. It is proved that the min–max and min–max regret versions with nonnegative edge costs are hard to approximate within for any unless the problems in NP have quasi-polynomial time algorithms. Similarly, the 2-stage min–max problem cannot be approximated within unless the problems in NP have quasi-polynomial time algorithms. In this paper randomized LP-based approximation algorithms with performance bound of for min–max and 2-stage min–max problems are also proposed. [ABSTRACT FROM AUTHOR]

In this paper, we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is -hard for general topologies, but optimal and near-optimal solutions have been provided for particular networks. In this paper, the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes, and pyramid networks. For the two-dimensional meshes of trees the results are optimal; for the higher-dimensional meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, there remains a small factor between the upper and the lower bounds. [Copyright &y& Elsevier]

Abstract: Geiringer''s theorem is a statement which tells us something about the limiting frequency of occurrence of a certain individual when a classical genetic algorithm is executed in the absence of selection and mutation. Recently Poli, Stephens, Wright and Rowe extended the original theorem of Geiringer to include the case of variable-length genetic algorithms and linear genetic programming. In the current paper a rather powerful finite population version of Geiringer''s theorem which has been established recently by Mitavskiy is used to derive a schema-based version of the theorem for nonlinear genetic programming with homologous crossover. The theorem also applies in the presence of “node mutation”. The corresponding formula in case when “node mutation” is present has been established. The limitation of the finite population Geiringer result is that it applies only in the absence of selection. In the current paper we also observe some general inequalities concerning the stationary distribution of the Markov chain associated to an evolutionary algorithm in which selection is the last (output) stage of a cycle. Moreover we prove an “anti-communism” theorem which applies to a wide class of EAs and says that for small enough mutation rate, the stationary distribution of the Markov chain modelling the EA cannot be uniform. [Copyright &y& Elsevier]

The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal-dual approximation algorithms with approximation ratios of 2 and 4, respectively. [ABSTRACT FROM AUTHOR]

In some application cases, the solutions of combinatorial optimization problems on graphs should satisfy an additional vertex size constraint. In this paper, we consider size-constrained minimum s – t cut problems and size-constrained dense subgraph problems. We introduce the minimum s – t cut with at-least- k vertices problem, the minimum s – t cut with at-most- k vertices problem, and the minimum s – t cut with exactly k vertices problem. We prove that they are NP -complete. Thus, they are not polynomially solvable unless P = NP . On the other hand, we also study the densest at-least- k -subgraph problem (DalkS) and the densest at-most- k -subgraph problem (DamkS) introduced by Andersen and Chellapilla [1] . We present a polynomial time algorithm for DalkS when k is bounded by some constant c . We also present two approximation algorithms for DamkS. The first approximation algorithm for DamkS has an approximation ratio of n − 1 k − 1 , where n is the number of vertices in the input graph. The second approximation algorithm for DamkS has an approximation ratio of O ( n δ ) , for some δ < 1 / 3 . [ABSTRACT FROM AUTHOR]

We consider a variant of the Bin Packing Problem dealing with fragmentable items. Given a fixed number of bins, the objective is to put all the items into the bins by splitting them in a minimum number of fragments. This problem is useful for modeling splittable resource allocation. In this paper we introduce the problem and its complexity. We give and prove several properties then we present various approximation algorithms and specially a 6 5 -approximation algorithm. [ABSTRACT FROM AUTHOR]

Thue proved that the factors occurring infinitely many times in square-free words over { 0 , 1 , 2 } avoiding the factors in { 010 , 212 } are the factors of the fixed point of the morphism 0 ↦ 012 , 1 ↦ 02 , 2 ↦ 1 . He similarly characterized square-free words avoiding { 010 , 020 } and { 121 , 212 } as the factors of two morphic words. In this paper, we exhibit smaller morphisms to define these two square-free morphic words and we give such characterizations for six types of binary words containing few distinct squares. [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems with uncertain costs is discussed. The uncertainty is modeled by specifying a discrete scenario set containing K distinct cost scenarios. The Ordered Weighted Averaging (OWA for short) aggregation operator is applied to choose a solution. Some well known criteria used in decision making under uncertainty such as the maximum, minimum, average, Hurwicz and median are special cases of OWA. Furthermore, by using OWA, the traditional robust (min–max) approach to combinatorial optimization problems with uncertain costs can be generalized. The computational complexity and approximability of the problem of minimizing OWA for the considered class of problems are investigated and some new positive and negative results in this area are provided. These results remain valid for many basic problems, such as network or resource allocation problems. [ABSTRACT FROM AUTHOR]

Abstract: This paper tackles the following problem: given a connected graph with a weight function on its edges and an integer , find a partition of V into k clusters such that the sum (over all pairs of clusters) of the heaviest edges between the clusters is minimized. We first prove that this problem (and even the unweighted variant) cannot be approximated within a factor of unless , and cannot admit an algorithm unless . Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than . Concerning the unweighted version of the problem, we study how the diameter of the input graph can influence its complexity, by obtaining negative results for graphs of low diameter, positive results for graphs of high diameter, and a polynomial-time approximation algorithm with an approximation ratio smaller than and depending on the diameter. We also highlight a link between the k -sparsest subgraph problem and the unweighted version. This allows us to develop several constant ratio approximation algorithms running in exponential time for general graphs, and in polynomial time in some restricted graph classes. Finally, we discuss the exact resolution for fixed k and the connections to a graph homomorphism problem. [Copyright &y& Elsevier]

Abstract: The reoptimization issue studied in this paper can be described as follows: given an instance of some problem , an optimal solution for in and an instance resulting from a local modification of that consists of insertions or removals of a small number of data, we wish to use in order to solve in . The aim is to achieve either a better approximation ratio or a better running time (or both) than guaranteed by ex nihilo computation. We use this setting in order to study weighted versions of several representatives of a broad class of problems known in the literature as maximum induced hereditary subgraph problems. The main problems studied are max independent set, max -colorable subgraph and max split subgraph under vertex insertions and deletions. [Copyright &y& Elsevier]

Abstract: We consider a team of k identical, oblivious, and semi-synchronous mobile robots that are able to sense (i.e., view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size n. It is known that deterministic robots are necessary and sufficient to solve the problem, provided that k and n are coprime. By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive. [Copyright &y& Elsevier]

Abstract: We consider scheduling packets with values in a capacity-bounded buffer in an online setting. In this model, there is a buffer with limited capacity . At any time, the buffer cannot accommodate more than packets. Packets arrive over time. Each packet has a non-negative value. Packets leave the buffer only because they are either sent or dropped. Those packets that have left the buffer will not be reconsidered for delivery any more. In each time step, at most one packet in the buffer can be sent. The order in which the packets are sent should comply with the order of their arrival time. The objective is to maximize the total value of the packets sent in an online manner. In this paper, we study a variant of this FIFO buffering model in which a packet’s value is either 1 or . We present a deterministic memoryless 1.304-competitive algorithm. This algorithm has the same competitive ratio as the one presented in Lotker and Patt-Shamir [Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, in: Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing, PODC, 2002, pp. 134–142; Z. Lotker, B. Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, Computer Networks 17 (1) (2003) 77–89]. However, our algorithm is simpler and does not employ any marking bits. The idea used in our algorithm is novel and different from all previous approaches that have been applied for the general model and its variants. We do not proactively preempt one packet when a new packet arrives. Instead, we may preempt more than one 1-value packet at the time when the buffer contains sufficiently many -value packets. [Copyright &y& Elsevier]

Abstract: An edge subset of a connected graph is a -restricted edge cut if is disconnected, and every component of has at least vertices. The -restricted edge connectivity of G, denoted by , is the cardinality of a minimum -restricted edge cut. By the current studies on , it can be seen that the larger is, the more reliable the graph is. Hence one expects to be as large as possible. A possible upper bound for is defined as and is connected , where is the number of edges with one end in and the other end in , and is the subgraph of induced by . A graph is called -optimal if . A natural question is whether there exists a graph which is -optimal for any . In this paper, we show that except for two cases, the elementary Harary graph has this property. [Copyright &y& Elsevier]

Abstract: Black-box complexity, counting the number of queries needed to find the optimum of a problem without having access to an explicit problem description, was introduced by Droste, Jansen, and Wegener [S. Droste, T. Jansen, I. Wegener, Upper and lower bounds for randomized search heuristics in black-box optimization, Theory of Computing Systems 39 (2006) 525–544] to measure the difficulty of solving an optimization problem via generic search heuristics such as evolutionary algorithms, simulated annealing or ant colony optimization. Since then, a number of similar complexity notions were introduced. However, so far these new notions were only analyzed for artificial test problems. In this paper, we move a step forward and analyze the different black-box complexity notions for two classic combinatorial problems, namely the minimum spanning tree and the single-source shortest path problem. Besides proving bounds for their black-box complexities, our work reveals that the choice of how to model the optimization problem has a significant influence on its black-box complexity. In addition, when regarding the unbiased (symmetry-invariant) black-box complexity of combinatorial problems, it is important to choose a meaningful definition of unbiasedness. [Copyright &y& Elsevier]

Abstract: We consider the problem of searching for an unknown horizontal or vertical line in a plane. A search path in the plane starts at the origin and detects the unknown line, if the path hits the line for the first time. The performance of the search path is measured by competitive analysis. That is, we compute the ratio of the length of the path until the line is detected over the shortest path from the origin to the given line. The competitive ratio of a given search path is the worst-case ratio of the path among all horizontal and vertical lines in the plane. In this paper, we design a search path that attains a competitive ratio of , and slightly improves the current best-known search path. Furthermore, we prove that the search path is optimal among all paths that proceed in a cyclic manner. There is a strong conjecture that this path is the general optimal search path for searching axis-parallel lines. [Copyright &y& Elsevier]

Abstract: We introduce the vertex cover () problem, that is, the problem of finding a minimum weight set such that the graph has no , where is a path with vertices. The problem also has its application background. In this paper, we first show that the problem is NP-hard for any integer . Then we restrict our attention to the problem and give a 2-approximation algorithm using the primal–dual method. [Copyright &y& Elsevier]

Abstract: Given an -vertex directed graph and a set of requests, we consider assigning a set of edges to each vertex in so that for every request in the union of the edge sets assigned to and contains a path from to . The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general has lower and upper bounds on approximation ratio under the assumption . We then assume forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless . Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the maximum traveling salesman problem with -parameterized triangle inequality for , which means that the edge weights in the given complete graph satisfy for all distinct nodes . For the maximum traveling salesman problem with -parameterized triangle inequality, R. Hassin and S. Rubinstein gave a constant factor approximation algorithm with polynomial running time, they achieved a performance ratio only for in , which is the best known result. We design a -approximation algorithm for the maximum traveling salesman problem with -parameterized triangle inequality by using a similar idea but very different method to that in , where is an optimal solution of the minimum cycle cover in , which is better than the -approximation algorithm for almost all . [Copyright &y& Elsevier]

Abstract: Motivated by the constrained minimum spanning tree (CST) problem in Hassin and Levin [R. Hassin, A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on Computing 33 (2) (2004) 261–268], we study a new combinatorial optimization problem in this paper, called the general subdivision-constrained spanning tree problem (GSCST): given a graph with two nonnegative integers and for each edge , two positive integers and , the GSCST problem is to first find a spanning tree of with weight and then to insert some new vertices on some suitable edges in such that each edge in the subdivision tree of has its weight not beyond . The objective is to minimize the cost of such new vertices inserted on the suitable edges among all spanning trees of subject to the two preceding constraints, where a subdivision tree of is constructed by inserting some new vertices on the suitable edges in , the value is the least number of vertices inserted and is the cost of each vertex inserted on the edge . We obtain the following main results: (1) the GSCST problem and its variant are still NP-hard, by a reduction from the 0–1 knapsack problem, respectively; (2) the GSCST problem as well as its variant is polynomially equivalent to the CST problem, which implies the existence of a polynomial time approximation scheme to solve the GSCST problem and its variant; (3) we finally design three strongly polynomial time algorithms to solve the special versions of the GSCST problem and its variant, respectively. [Copyright &y& Elsevier]

Abstract: This paper presents strategies for improving the known upper and lower bounds for the bandwidth of Hamming graphs and . Our labeling strategy lowers the upper bound on the bandwidth of the continuous Hamming graph, , from .5 to .4497. A lower bound of .4439 on follows from known isoperimetric inequalities and a related dynamic program is conjectured to raise that lower bound to . In particular, showing the power of our method, we prove that the bandwidth of is exactly 101. [Copyright &y& Elsevier]

Abstract: The submodular function minimization problem (SFM) is a fundamental problem in combinatorial optimization and several fully combinatorial polynomial-time algorithms have recently been discovered to solve this problem. The most general versions of these algorithms are able to minimize any submodular function whose domain is a set of tuples over any totally-ordered finite set and whose range includes both finite and infinite values. In this paper we demonstrate that this general form of SFM is just one example of a much larger class of tractable discrete optimization problems defined by valued constraints. These tractable problems are characterized by the fact that their valued constraints have an algebraic property which we call a tournament pair multimorphism. This larger tractable class also includes the problem of satisfying a set of Horn clauses (Horn-SAT), as well as various extensions of this problem to larger finite domains. [Copyright &y& Elsevier]

Abstract: In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time. [Copyright &y& Elsevier]