Complexity results on restricted instances of a paint shop problem for words

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.     

Paintshop, odd cycles and necklace splitting

The following problem has been presented in [T. Epping, W. Hochstättler, P. Oertel, Complexity results on a paint shop problem, Discrete Applied Mathematics 136 (2004) 217-226] by Epping, Hochstättler and Oertel: cars have to be painted in two colors in a sequence where each car occurs twice; assign the two colors to the two occurrences of each car so as to minimize the number of color changes. More generally, the “paint shop scheduling problem” is defined with an arbitrary multiset of colors given for each car, where this multiset has the same size as the number of occurrences of the car; the mentioned article states two conjectures about the general problem and proves its NP-hardness. In a subsequent paper in [P. Bonsma, Th. Epping, W. Hochstättler, Complexity results for restricted instances of a paint shop problem for words, Discrete Applied Mathematics 154 (2006) 1335-1343], Bonsma, Epping and Hochstättler proved its APX-hardness and noticed the applicability of some classical results in special cases.We first identify the problem concerning two colors as a minimum odd circuit cover problem in particular graphs, exactly situating the problem. A resulting two-way reduction to a special minimum uncut problem leads to polynomial algorithms for subproblems, to observing APX-hardness through MAX CUT in 3-regular graphs, and to a solution with at most 3/4th of all possible remaining color changes (when all obliged color changes have been made).For the general problem concerning an arbitrary number of colors, we realize that the two aforementioned conjectures are corollaries of the celebrated “necklace splitting” theorem of Alon, Goldberg and West.     

Selecting Complementary Pairs of Literals

We present and rigorously analyze a heuristic that searches for a satisfying truth assignment of a given random instance of the 3-SAT problem. We prove that the heuristic asymptotically certainly succeeds in producing a satisfying truth assignment for formulas with clauses to variables ratio (density) of up to 3.52. Thus the experimentally observed threshold of the density where a typical formula's phase changes from asymptotically certainly satisfiable to asymptotically certainly contradictory is rigorously shown to be at least 3.52. The best previous lower bound in the long series of mathematically rigorous approximations by various research groups of the experimental threshold was 3.42. That was the first result where the probabilistic analysis was based on random formulas with a pre-specified, typical number of appearances for each literal. However, in that result, in order to simplify the analysis, the number of appearances of each literal was decoupled from the number of appearances of its negation. In this work, we assume not only that each literal has the typical number of occurrences, but that for each variable both numbers of occurrences of its positive and negated appearances are typical. By standard techniques, our algorithm can be easily modified to run in linear time. Thus not only the satisfiability threshold, but also the threshold (experimental again) where the complexity of searching for satisfying truth assignments jumps from polynomial to exponential is at least 3.52. This should be contrasted with the value 3.9 for the complexity threshold given by theoretical (but not mathematically rigorous) techniques of Statistical Physics.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

A heuristic approach for multiple item and location ordering problem with quantity discount and capacity constraint

This paper addresses a geographically distributed vending machine inventory control problem where the multiple product choices in every vending machine and the varied demand for each product in every location's vending machine exist. The ordering quantity for each product and the desirable number of each product type in a vending machine must be simultaneously decided to maximize the total expected profit. Considering that the ordering costs are in piece-wise function and only one type of product is allocated in a slot of a vending machine, the proposed problem correlates to the piece-wise constrained nonlinear integer-programming problem. There is difficulty in deriving the exact optimal solutions to this problem since its computational complexity appears to be a nondeterministic polynomial problem. This paper presents a novel heuristic approach in finding (1) the ordering quantity for each product, (2) the product types, and (3) the corresponding quantity allocated in each vending machine. The numerical results show the effectiveness of the proposed methodology in solving the aforementioned problem. In this paper, the solutions found by this study's approach are as well as those found by the brute-force method, and if not equivalent, perform better than those by the Lingo software.     

The joint distribution of the number of occurrences of two interrelated Poisson processes

The focus of this paper is the distribution for the number of occurrences of two independent but interrelated Poisson processes, to be named the joint imputed Poisson distribution. From its inception, the research was motivated by a problem facing the electric power industry. Power surges, which are observable, represent occurrences of the imputing process. Circuit breaker breakdowns, which cannot be seen taking place, constitute occurrences of the imputed process. Though not observable, at each occurrence of the imputing process, knowledge about the imputed process is obtained. Occurrences of the imputed process are revealed only as the result of periodic inspection, or with far greater cost at the subsequent occurrence of the imputing process. A comprehensive treatment of the joint imputed Poisson distribution for the number of occurrences of the two processes over a fixed time period was presented by Cuffe. Because these probabilistic results had to be derived from first principles, a lengthy, rigorous mathematical exposition is not appropriate in this forum. Rather, we concentrate here on a presentation of results with only highlights of their proofs.     

Neighborhood functions and hill-climbing strategies dedicated to the generalized ungapped local multiple alignment

Ungapped Local Multiple Alignment is a widely used procedure in bioinformatics. It roughly consists of locating in a given set of nucleotide (DNA) or amino acid (proteins) sequences, a number of non-overlapping fixed-size factors (also called occurrences), that are likely to have evolved from a common ancestor. In addition to the widely known statistical approaches, we define the problem from a pure combinatorial optimization point of view, by defining specific neighborhood functions and a hill-climbing strategy for each of four particular instances of this problem: (1) one occurrence per sequence, (2) at most one occurrence per sequence, (3) at least one occurrence per sequence, and (4) any number of occurrences per sequence. The method is implemented in a tool called Nomad (Neighborhood Optimization for Multiple Alignment Discovery) and a web interface is available at www.expasy.org/tools/nomad.html.     

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP∩CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity , which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).     

Inferring a graph from path frequency

This paper considers the problem of inferring a graph from the number of occurrences of vertex-labeled paths, which is closely related to the pre-image problem for graphs: to reconstruct a graph from its feature space representation. It is shown that both exact and approximate versions of the problem can be solved in polynomial time in the size of an output graph by using dynamic programming algorithms if the graphs are trees whose maximum degree is bounded by a constant and the lengths of given paths and alphabet size are bounded by constants. On the other hand, it is shown that this problem is strongly NP-hard even for trees of bounded degree if the maximum length of paths is not bounded. The problem of inferring a string from the number of occurrences of fixed size substrings is also studied.     

Set-Up Coordination between Two Stages of a Supply Chain

In the material flow of a plant, parts are processed in batches, each having two distinct attributes, say shape and color. In one department, a set-up occurs every time the shape of the new batch is different from the previous one. In a downstream department, there is a set-up when the color of the new batch is different from the previous one. Since a unique sequence of batches must be established, the problem consists in finding such a common sequence optimizing an overall utility index. Here we consider two indices, namely the total number of set-ups and the maximum number of set-ups between the two departments. Both problems are shown to be NP-hard. An efficient heuristic approach is presented for the first index which allows to solve a set of real-life instances and performs satisfactorily on a large sample of experimental data.     

Solving Graph Coloring Problems with the Douglas-Rachford Algorithm

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.     

On coloring problems with local constraints

We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3–16].     

Graph unique-maximum and conflict-free colorings

We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.     

Competitive subset selection with two agents

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).     

Fuzzy measures for color image retrieval

In this paper we present a scheme for fuzzy similarity based strategy to retrieve an image from a library of color images. Color features are among the most important features used in image database retrieval. Due to its compact representation and low complexity, direct histogram comparison is the most commonly used technique in measuring color similarity of images. A gamma membership function, derived from the Gamma distribution, has been proposed to find the membership values of the gray levels of the histogram. We present here an image retrieval scheme with some popular vector fuzzy distance measures using a gamma membership function for finding the membership values of the gray levels and evaluate the matching function to select the appropriate retrieval mechanism.     

Inexact Alternating-Direction-Based Contraction Methods for Separable Linearly Constrained Convex Optimization

Alternating direction method of multipliers has been well studied in the context of linearly constrained convex optimization. In the last few years, we have witnessed a number of novel applications arising from image processing, compressive sensing and statistics, etc., where the approach is surprisingly efficient. In the early applications, the objective function of the linearly constrained convex optimization problem is separable into two parts. Recently, the alternating direction method of multipliers has been extended to the case where the number of the separable parts in the objective function is finite. However, in each iteration, the subproblems are required to be solved exactly. In this paper, by introducing some reasonable inexactness criteria, we propose two inexact alternating-direction-based contraction methods, which substantially broaden the applicable scope of the approach. The convergence and complexity results for both methods are derived in the framework of variational inequalities.     

Variable space search for graph coloring

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the k-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The k-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

Separating words by occurrences of subwords

We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered.