Are there more almost separable partitions than separable partitions?

A partition of a set of n points in d-dimensional space into p parts is called an (almost) separable partition if the convex hulls formed by the parts are (almost) pairwise disjoint. These two partition classes are the most encountered ones in clustering and other partition problems for high-dimensional points and their usefulness depends critically on the issue whether their numbers are small. The problem of bounding separable partitions has been well studied in the literature (Alon and Onn in Discrete Appl. Math. 91:39–51, 1999; Barnes et al. in Math. Program. 54:69–86, 1992; Harding in Proc. Edinb. Math. Soc. 15:285–289, 1967; Hwang et al. in SIAM J. Optim. 10:70–81, 1999; Hwang and Rothblum in J. Comb. Optim. 21:423–433, 2011a). In this paper, we prove that for d≤2 or p≤2, the maximum number of almost separable partitions is equal to the maximum number of separable partitions.     

A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP

We present a primal-dual ?log(n)?-approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. The previous algorithm for the problem (V.H. Nguyen and T.T Nguyen in Int. J. Math. Oper. Res. 4(3):294–301, 2012) which is not combinatorial, is based on the Held-Karp relaxation and heuristic methods such as the Frieze et al.’s heuristic (Frieze et al. in Networks 12:23–39, 1982) or the recent Asadpour et al.’s heuristic for the ATSP (Asadpour et al. in 21st ACM-SIAM symposium on discrete algorithms, 2010). Depending on which of the two heuristics is used, it gives respectively 1+?log(n)? and $3+ 8\frac{\log(n)}{\log(\log(n))}$ as an approximation ratio. Our algorithm achieves an approximation ratio of ?log(n)? which is weaker than $3+ 8\frac{\log(n)}{\log(\log(n))}$ but represents the first combinatorial approximation algorithm for the Asymmetric Prize-Collecting TSP.     

Some results on the target set selection problem

In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009).     

A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let \((MQP)\) be a general mixed-integer quadratic program that consists of minimizing a quadratic function \(f(x) = x^TQx +c^Tx\) subject to linear constraints. Our approach to solve \((MQP)\) is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables \(y_{ij}\) , additional quadratic constraints \(y_{ij}=x_ix_j\) , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381–401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints \(y_{ij}=x_ix_j\) to solve \((MQP)\) . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user’s manual, 2010).     

Shifting strategy for geometric graphs without?geometry

We give a simple framework which is an alternative to the celebrated and widely used shifting strategy of Hochbaum and Maass (J. ACM 32(1):103?C136, 1985) which has yielded efficient algorithms with good approximation bounds for numerous optimization problems in low-dimensional Euclidean space. Our framework does not require the input graph/metric to have a geometric realization??it only requires that the input graph satisfy some weak property referred to as growth boundedness. Growth bounded graphs form an important graph class that has been used to model wireless networks. We show how to apply the framework to obtain a polynomial time approximation scheme (PTAS) for the maximum (weighted) independent set problem on this important graph class; the problem is W[1]-complete. Via a more sophisticated application of our framework, we show how to obtain a PTAS for the maximum (weighted) independent set for intersection graphs of (low-dimensional) fat objects that are expressed without geometry. Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) and Chan (J. Algorithms 46(2):178?C189, 2003) independently gave a PTAS for maximum weighted independent set problem for intersection graphs of fat geometric objects, say ball graphs, which required a geometric representation of the input. Our result gives a positive answer to a question of Erlebach et al. (SIAM J. Comput. 34(6):1302?C1323, 2005) who asked if a PTAS for this problem can be obtained without access to a geometric representation.     

(1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation

This paper studies the online Orthogonal Variable Spreading Factor (OVSF) code assignment problem with resource augmentation introduced by Erlebach et al. (in STACS 2004. LNCS, vol. 2996, pp. 270–281, 2004). We propose a (1+1/α)-competitive algorithm with help of (1+?α?)lg^? h trees for the height h of the OVSF code tree and any α≥1. In other words, it is a (1+ε)-competitive algorithm with help of (1+?1/ε?)lg^? h trees for any constant 0<ε≤1. In the case of α=1 (or ε=1), we obtain a 2-competitive algorithm with 2lg^? h trees, which substantially improves the previous resource of 3h/8+2 trees shown by Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). In another aspect, if it is not necessary to bound the incurred cost for individual requests to a constant, an amortized (4/3+δ)-competitive algorithm with (11/4+4/(3δ)) trees for any 0<δ≤4/3 is also designed in Chan et al. (COCOON 2009. LNCS, vol. 5609, pp. 358–367, 2009). The algorithm in this paper gives us a new trade-off between the competitive ratio and the resource augmentation when α≥3 (or ε≤1/3), although the incurred cost for individual requests is bounded to a constant.     

Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of \(\alpha + 4\) for the robust fault-tolerant facility location problem, which is best so far.     

Approximation algorithm for uniform bounded facility location problem

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

Clustering with or without the approximation

We study algorithms for clustering data that were recently proposed by Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) and that have already given rise to several follow-up papers. The input for the clustering problem consists of points in a metric space and a number k, specifying the desired number of clusters. The algorithms find a clustering that is provably close to a target clustering, provided that the instance has the “(1+α,ε)-property”, which means that the instance is such that all solutions to the k-median problem for which the objective value is at most (1+α) times the optimal objective value correspond to clusterings that misclassify at most an ε fraction of the points with respect to the target clustering. We investigate the theoretical and practical implications of their results. Our main contributions are as follows. First, we show that instances that have the (1+α,ε)-property and for which, additionally, the clusters in the target clustering are large, are easier than general instances: the algorithm proposed in Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) is a constant factor approximation algorithm with an approximation guarantee that is better than the known hardness of approximation for general instances. Further, we show that it is NP-hard to check if an instance satisfies the (1+α,ε)-property for a given (α,ε); the algorithms in Balcan et al. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) need such α and ε as input parameters, however. We propose ways to use their algorithms even if we do not know values of α and ε for which the assumption holds. Finally, we implement these methods and other popular methods, and test them on real world data sets. We find that on these data sets there are no α and ε so that the dataset has both (1+α,ε)-property and sufficiently large clusters in the target solution. For the general case where there are no assumptions about the cluster sizes, we show that on our data sets the performance guarantee proved by Balcan et a. (SODA’09: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1068–1077, 2009a) is meaningless for the values of α,ε for which the data set has the (1+α,ε)-property. The algorithm nonetheless gives reasonable results, although it is outperformed by other methods.     

Acyclic edge coloring of planar graphs without a 3-cycle adjacent to a 6-cycle

An acyclic edge coloring of a graph \(G\) is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index \(a'(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has an acyclic edge coloring using \(k\) colors. Fiam? ik (Math Slovaca 28:139–145, 1978) and later Alon et al. (J Graph Theory 37:157–167, 2001) conjectured that \(a'(G)\le \Delta +2\) for any simple graph \(G\) with maximum degree \(\Delta \) . In this paper, we confirm this conjecture for planar graphs without a \(3\) -cycle adjacent to a \(6\) -cycle.     

A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio $O(\sqrt{q})$ , where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log² n)), our approximation ratio $O(\sqrt{q})$ is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.     

Independent dominating sets in regular graphs

Let G be a simple, regular graph of order n and degree δ. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish new upper bounds, as functions of n and δ, for the independent domination number of regular graphs with $n/6<\delta< (3-\sqrt{5})n/2$ . Our two main theorems complement recent results of Goddard et al. (Ann. Comb., 2011) for larger values of δ.     

Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems

We consider the max-bisection problem and the disjoint 2-catalog segmentation problem, two well-known NP-hard combinatorial optimization problems. For the first problem, we apply the semidefinite programming (SDP) relaxation and the RPR² technique of Feige and Langberg (J. Algorithms 60:1–23, 2006) to obtain a performance curve as a function of the ratio of the optimal SDP value over the total weight through finer analysis under the assumption of convexity of the RPR² function. This ratio is shown to be in the range of [0.5,1]. The performance curve implies better approximation performance when this ratio is away from 0.92, corresponding to the lowest point on this curve with the currently best approximation ratio of 0.7031 due to Feige and Langberg (J. Algorithms 60:1–23, 2006). For the second problem, similar technique results in an approximation ratio of 0.7469, improving the previously best known result 0.7317 due to Wu et al. (J. Ind. Manag. Optim. 8:117–126, 2012).     

Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five

An adjacent vertex distinguishing edge coloring of a graph \(G\) is a proper edge coloring of \(G\) such that any pair of adjacent vertices admit different sets of colors. The minimum number of colors required for such a coloring of \(G\) is denoted by \(\chi ^{\prime }_{a}(G)\) . In this paper, we prove that if \(G\) is a planar graph with girth at least 5 and \(G\) is not a 5-cycle, then \(\chi ^{\prime }_{a}(G)\le \Delta +2\) , where \(\Delta \) is the maximum degree of \(G\) . This confirms partially a conjecture in Zhang et al. (Appl Math Lett 15:623–626, 2002).     

Scheduling Packets with Values and Deadlines in Size-Bounded Buffers

Motivated by providing quality-of-service differentiated services in the Internet, we consider buffer management algorithms for network switches. We study a multi-buffer model. A network switch consists of multiple size-bounded buffers such that at any time, the number of packets residing in each individual buffer cannot exceed its capacity. Packets arrive at the network switch over time; they have values, deadlines, and designated buffers. In each time step, at most one pending packet is allowed to be sent and this packet can be from any buffer. The objective is to maximize the total value of the packets sent by their respective deadlines. A 9.82-competitive online algorithm (Azar and Levy in Lect Notes Comput Sci 4059:5–16 2006) and a 4.73-competitive online algorithm (Li in Lect Notes Comput Sci 5564:265–278, 2009) have been provided for this model, but no offline algorithms have yet been described. In this paper, we study the offline setting of the multi-buffer model. Our contributions include a few optimal offline algorithms for some variants of the model. Each variant has its unique and interesting algorithmic feature.     

The power of “mapping the territory”. Why economists should become more aware of the performativity of their models

Economics is not simply about representing reality; it is also about shaping it, an approach encapsulated in Donald MacKenzie’s aphorism that economics is best conceived as an “engine, not as a camera” (MacKenzie and Millo (Am J Sociol 109(1):107–145, 2003). The making and application of economic theories and models contribute actively and intentionally towards the making of our social world, by encouraging, guiding and legitimizing actions and decisions, or discouraging others, and by steering them in certain directions. It follows that economists do not simply draw maps of the economic territory within their compass: they are not straightforwardly the cartographers of the economy, and cannot be seen as the disinterested observers that they commonly represent themselves to be, and indeed are often thought of as. Their theoretical work has or aims at practical consequences for the economy, and indeed for society at large, and their interests and influence are thus by no means confined to academia alone. This article calls for a discussion of the ethical responsibilities of economists, and of economics, and challenges the discipline properly to assume those responsibilities; and it concludes by considering the key questions—what makes a ‘good’ economic model; and what criteria should be used to distinguish the good models, and the ‘good ways’ of handling models and their results, from the bad ones. As far as epistemology, the methodology of research programmes and the relation of theory and (social) practice are concerned, the insights of mainly von Hayek (Br J Philos Sci 6(23):209–225, 1955, The pretence of knowledge. Lecture to the memory of Alfred Nobel, 1974; Individualism and economic order, University of Chicago Press, Chicago, pp 33–56, 1980a; Individualism and economic order, University of Chicago Press, Chicago, pp 57–76, 1980b; The theory of complex phenomena. Readings in the philosophy of social science, MIT Press, Cambridge, 1994) and Popper (e.g. The myth of the framework: in defence of science and rationality, Routledge, New York 1994a; Models, instruments, and truth. The status of the rationality principle in the social sciences, pp 154–184, 1994b) provide the background of my discussion of the mentioned issues.     

Chromatic number of distance graphs generated by the sets {2,3,x,y}

Let D be a set of positive integers. The distance graph generated by D has all integers ? as the vertex set; two vertices are adjacent whenever their absolute difference falls in D. We completely determine the chromatic number for the distance graphs generated by the sets D={2,3,x,y} for all values x and y. The methods we use include the density of sequences with missing differences and the parameter involved in the so called “lonely runner conjecture”. Previous results on this problem include: For x and y being prime numbers, this problem was completely solved by Voigt and Walther (Discrete Appl. Math. 51:197–209, 1994); and other results for special integers of x and y were obtained by Kemnitz and Kolberg (Discrete Math. 191:113–123, 1998) and by Voigt and Walther (Discrete Math. 97:395–397, 1991).     

(p,q)-total labeling of complete graphs

Given a graph G and positive integers p,q with p≥q, the (p,q)-total number $\lambda_{p,q}^{T}(G)$ of G is the width of the smallest range of integers that suffices to label the vertices and the edges of G such that the labels of any two adjacent vertices are at least q apart, the labels of any two adjacent edges are at least q apart, and the difference between the labels of a vertex and its incident edges is at least p. Havet and Yu (Discrete Math 308:496–513, 2008) first introduced this problem and determined the exact value of $\lambda_{p,1}^{T}(K_{n})$ except for even n with p+5≤n≤6p ²?10p+4. Their proof for showing that $\lambda _{p,1}^{T}(K_{n})\leq n+2p-3$ for odd n has some mistakes. In this paper, we prove that if n is odd, then $\lambda_{p}^{T}(K_{n})\leq n+2p-3$ if p=2, p=3, or $4\lfloor\frac{p}{2}\rfloor+3\leq n\leq4p-1$ . And we extend some results that were given in Havet and Yu (Discrete Math 308:496–513, 2008). Beside these, we give a lower bound for $\lambda_{p,q}^{T}(K_{n})$ under the condition that q<p<2q.     

A note on anti-coordination and social interactions

This note confirms a conjecture of (Bramoullé in Games Econ Behav 58:30–49, 2007). The problem, which we name the maximum independent cut problem, is a restricted version of the MAX-CUT problem, requiring one side of the cut to be an independent set. We show that the maximum independent cut problem does not admit any polynomial time algorithm with approximation ratio better than n ^1?? , where n is the number of nodes, and ? arbitrarily small, unless $\mathrm{P} = \mathrm{NP}$ . For the rather special case where each node has a degree of at most four, the problem is still APX-hard.     

Equivalence of two conjectures on equitable coloring of graphs

A graph G is said to be equitably k-colorable if there exists a proper k-coloring of G such that the sizes of any two color classes differ by at most one. Let Δ(G) denote the maximum degree of a vertex in G. Two Brooks-type conjectures on equitable Δ(G)-colorability have been proposed in Chen and Yen (Discrete Math., 2011) and Kierstead and Kostochka (Combinatorica 30:201–216, 2010) independently. We prove the equivalence of these conjectures.