ALLIANCES BETWEEN COMPETITORS AND CONSUMER INFORMATION

Alliances between competitors in which established firms provide access to proprietary resources—for example, their distribution channels—are important business practices. We analyze a market where an established firm, firm A, produces a product of well‐known quality, and a firm with an unknown brand, firm B, has to choose to produce high or low quality. Firm A observes firm B's quality choice but consumers do not. Hence, firm B is subject to a moral hazard problem which can potentially be solved by firm A. Firm A can accept or reject to form an alliance with firm B, which is observed by consumers. If an alliance is formed, firm A implicitly certifies the rival's product. Consumers infer that firm B is a competitor with high quality, because otherwise why would the established firm accept to form an alliance? The mechanism we discover allows for an economic interpretation of several types of business practices. (JEL: L15, L13, L24, L42, M21, M31, D43)     

Maximum <Emphasis Type="Italic">k</Emphasis>-regular induced subgraphs

Independent sets, induced matchings and cliques are examples of regular induced subgraphs in a graph. In this paper, we prove that finding a maximum cardinality k-regular induced subgraph is an NP-hard problem for any fixed value of k. We propose a convex quadratic upper bound on the size of a k-regular induced subgraph and characterize those graphs for which this bound is attained. Finally, we extend the Hoffman bound on the size of a maximum 0-regular subgraph (the independence number) from k=0 to larger values of k.     

Inapproximability results for the lateral gene transfer problem

This paper concerns the Lateral Gene Transfer Problem. This minimization problem, defined by Hallett and Lagergren (2001), is that of finding the most parsimonious lateral gene transfer scenario for a given pair of gene and species trees. Our main results are the following:

Attacking the Market Split Problem with Lattice Point Enumeration

The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.     

Parameterized lower bound and inapproximability of polylogarithmic string barcoding

String barcoding is a method that can identify microorganisms by analyzing their genome sequences. In this paper, we study the polylogarithmic string barcoding problem, where the lengths of the substrings in the testing set are polylogarithmically bounded. In particular, we show that the polylogarithmic string barcoding problem remains NP-hard and moreover, for a problem instance with n sequences, it is NP-hard to achieve an approximate ratio within dln n in polynomial time, where d is some constant. We then consider the parameterized polylogarithmic string barcoding problem, where the number of substrings in the test set is considered to be a fixed parameter k. We show that, unless W[2]=FPT, there does not exist a 2 ^O(k) n ^c algorithm that can decide whether a test set of size k exists or not, where c is a constant independent of n and k.     

Estimated Rate of Fatal Automobile Accidents Attributable to Acute Solvent Exposure at Low Inhaled Concentrations

Acute solvent exposures may contribute to automobile accidents because they increase reaction time and decrease attention, in addition to impairing other behaviors. These effects resemble those of ethanol consumption, both with respect to behavioral effects and neurological mechanisms. These observations, along with the extensive data on the relationship between ethanol consumption and fatal automobile accidents, suggested a way to estimate the probability of fatal automobile accidents from solvent inhalation. The problem can be approached using the logic of the algebraic transitive postulate of equality: if A=B and B=C, then A=C. We first calculated a function describing the internal doses of solvent vapors that cause the same magnitude of behavioral impairment as ingestion of ethanol (A=B). Next, we fit a function to data from the literature describing the probability of fatal car crashes for a given internal dose of ethanol (B=C). Finally, we used these two functions to generate a third function to estimate the probability of a fatal car crash for any internal dose of organic solvent vapor (A=C). This latter function showed quantitatively (1) that the likelihood of a fatal car crash is increased by acute exposure to organic solvent vapors at concentrations less than 1.0 ppm, and (2) that this likelihood is similar in magnitude to the probability of developing leukemia from exposure to benzene. This approach could also be applied to other potentially adverse consequences of acute exposure to solvents (e.g., nonfatal car crashes, property damage, and workplace accidents), if appropriate data were available.     

Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function 〈x, Ax〉 + 〈c, x〉 over the set {0,1} ⁿ where c is a vector in ℝ ⁿ and A is a symmetric real n × n matrix of constant rank r. We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. We then derive two new classes of special cases of the CR-QP01 which can be solved in polynomial time. These classes result from further restrictions on the matrix A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A and extend the range of applicability of the latter algorithm. It turns out that neither of the two algorithms dominates the other with respect to the class of instances which can be solved in polynomial time.     

The bandpass problem: combinatorial optimization and library of problems

A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows. The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number of bandpasses having the same given bandpass number in all columns. This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic solutions has been confirmed in the extensive computational experiments. As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without.     

Two-agent scheduling of time-dependent jobs

We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.     

Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within \((\alpha ,1/2]\) where \(0 \le \alpha < 1/2 \), and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.     

Is There a Curse of Dimensionality for Contraction Fixed Points in the Worst Case?

This paper analyzes the complexity of the contraction fixed point problem: compute an ε‐approximation to the fixed point V*Γ(V*) of a contraction mapping Γ that maps a Banach space B_d of continuous functions of d variables into itself. We focus on quasi linear contractions where Γ is a nonlinear functional of a finite number of conditional expectation operators. This class includes contractive Fredholm integral equations that arise in asset pricing applications and the contractive Bellman equation from dynamic programming. In the absence of further restrictions on the domain of Γ, the quasi linear fixed point problem is subject to the curse of dimensionality, i.e., in the worst case the minimal number of function evaluations and arithmetic operations required to compute an ε‐approximation to a fixed point V*∈B_d increases exponentially in d. We show that the curse of dimensionality disappears if the domain of Γ has additional special structure. We identify a particular type of special structure for which the problem is strongly tractable even in the worst case, i.e., the number of function evaluations and arithmetic operations needed to compute an ε‐approximation of V* is bounded by Cε^−p where C and p are constants independent of d. We present examples of economic problems that have this type of special structure including a class of rational expectations asset pricing problems for which the optimal exponent p1 is nearly achieved.     

On the number of separable partitions

Consider partitions of a given set A of n distinct points in general position in ℝ ^d into parts where each pair of parts can be separated by a hyperplane that contains a given set of points E. We consider the problem of counting and generating all such partitions (correcting a classic 1967 result of Harding about the number of such partitions into two parts). Applications of the result to partition problems are presented.     

AN EMPIRICAL EXAMINATION OF SOCIAL POWER IN TERMS OF DECISION THEORY1

The paper presents an extension of decision theory to the analysis of social power. The power of a person, A, over another person, B, is viewed in terms of the effect A has on B's decision. The analysis is based on the idea that B's decision regarding the performance of alternative behaviors is a function of 1) B's utility for the consequences of the behaviors and 2) B's subjective probabilities that the behaviors will lead to these consequences. In these terms, A's power over B lies in A's ability to mediate various consequences for B, contingent upon B's compliance or noncompliance. Subjects were asked to consider eight situations in which hypothetical individuals had to make a choice between two courses of action. In each situation another person (A) was attempting to induce the hypothetical individual (B) to choose one of the alternatives, while various situational factors were influencing B to choose the other alternative. The subjects were asked to consider B's utilities and subjective probabilities in each situation and to indicate whether or not B should comply with A and to make ratings of A's power. The decision theory analysis did well in predicting whether or not subjects would indicate that B should comply with A. Also, subjects generally were able to correctly specify whether A or the situational factors had more influence over B's decision. Finally, the subjects' ratings of A's power in the eight situations were highly related to the decision theoretic measure of power.     

Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

Constant time approximation scheme for largest well predicted subset

The largest well predicted subset problem is formulated for comparison of two predicted 3D protein structures from the same sequence. A 3D protein structure is represented by an ordered point set A={a ₁,…,a _n }, where each a _i is a point in 3D space. Given two ordered point sets A={a ₁,…,a _n } and B={b ₁,b ₂,…b _n } containing n points, and a threshold d, the largest well predicted subset problem is to find the rigid body transformation T for a largest subset B _opt of B such that the distance between a _i and T(b _i ) is at most d for every b _i in B _opt . A meaningful prediction requires that the size of B _opt is at least αn for some constant α (Li et al. in CPM 2008, 2008). We use LWPS(A,B,d,α) to denote the largest well predicted subset problem with meaningful prediction. An (1+δ ₁,1?δ ₂)-approximation for LWPS(A,B,d,α) is to find a transformation T to bring a subset B′?B of size at least (1?δ ₂)|B _opt | such that for each b _i ∈B′, the Euclidean distance between the two points distance?(a _i ,T(b _i ))≤(1+δ ₁)d. We develop a constant time (1+δ ₁,1?δ ₂)-approximation algorithm for LWPS(A,B,d,α) for arbitrary positive constants δ ₁ and δ ₂. To our knowledge, this is the first constant time algorithm in this area. Li et al. (CPM 2008, 2008) showed an $O(n(\log n)^{2}/\delta_{1}^{5})$ time randomized (1+δ ₁)-distance approximation algorithm for the largest well predicted subset problem under meaningful prediction. We also study a closely related problem, the bottleneck distance problem, where we are given two ordered point sets A={a ₁,…,a _n } and B={b ₁,b ₂,…b _n } containing n points and the problem is to find the smallest d _opt such that there exists a rigid transformation T with distance(a _i ,T(b _i ))≤d _opt for every point b _i ∈B. A (1+δ)-approximation for the bottleneck distance problem is to find a transformation T, such that for each b _i ∈B, distance?(a _i ,T(b _i ))≤(1+δ)d _opt , where δ is a constant. For an arbitrary constant δ, we obtain a linear O(n/δ ⁶) time (1+δ)-algorithm for the bottleneck distance problem. The best known algorithms for both problems require super-linear time (Li et al. in CPM 2008, 2008).     

On the Bandpass problem

The complexity of the Bandpass problem is re-investigated. Specifically, we show that the problem with any fixed bandpass number B≥2 is NP-hard. Next, a row stacking algorithm is proposed for the problem with three columns, which produces a solution that is at most 1 less than the optimum. For the special case B=2, the row stacking algorithm guarantees an optimal solution. On approximation, for the general problem, we present an O(B ²)-algorithm, which reduces to a 2-approximation algorithm for the special case B=2.     

Relative Utilitarianism

‘If empirically meaningful interpersonal comparisons have to be based on indifference maps, as we have argued, then the Independence of Irrelevant Alternatives must be violated. The information which enables us to assert that individual A prefers x to y more strongly than B prefers y to x must be based on comparisons by A and B of x and y not only to each other but also to other alternatives. Kenneth J. Arrow, ‘Social Choice and Individual Values, p. 112. In a framework of preferences over lotteries, we show that an axiom system consisting of weakened versions of Arrow's axioms has a unique solution. ‘Relative Utilitarianism’ consists of first normalizing individual von Neumann-Morgenstern utilities between 0 and 1 and then summing them.     

Batch-Processing Scheduling with Setup Times

The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time.     

RNA multiple structural alignment with longest common subsequences

In this paper, we present a new model for RNA multiple sequence structural alignment based on the longest common subsequence. We consider both the off-line and on-line cases. For the off-line case, i.e., when the longest common subsequence is given as a linear graph with n vertices, we first present a polynomial O(n ²) time algorithm to compute its maximum nested loop. We then consider a slightly different problem—the Maximum Loop Chain problem and present an algorithm which runs in O(n ⁵) time. For the on-line case, i.e., given m RNA sequences of lengths n, compute the longest common subsequence of them such that this subsequence either induces a maximum nested loop or the maximum number of matches, we present efficient algorithms using dynamic programming when m is small. This research is partially supported by EPSCOR Visiting Scholar's Program and MSU Short-term Professional Development Program.