Search

We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (WINE 2013) to model the impact of asymmetric information on the revenue of the seller in take-it-or-leave-it sales. Instances of the problem consist of an $n \times m$ binary matrix $A$ and a probability distribution over its columns. A partition scheme $B=(B_1,...,B_n)$ consists of a partition $B_i$ for each row $i$ of $A$. The partition $B_i$ acts as a smoothing operator on row $i$ that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme $B$ that induces a smooth matrix $A^B$, the partition value is the expected maximum column entry of $A^B$. The objective is to find a partition scheme such that the resulting partition value is maximized. We present a $9/10$-approximation algorithm for the case where the probability distribution is uniform and a $(1-1/e)$-approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization., Comment: 17 pages

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|2) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X 1,…,X g ⊆V, with each group X i having a requirement r i between 0 and |X i |. The goal is to find a minimum cost set of edges whose removal separates each group X i into at least r i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.

An important characteristic of distributed grids is that they allow geographically separated multicomputers to be tied together in a transparent virtual environment to solve large-scale computational problems. However, many of these applications require effective runtime load balancing for the resulting solutions to be viable. In this paper we present a novel latency-tolerant partitioner, called MinEX, that dynamically balances processor workloads while minimizing data movement and runtime communication for applications that are executed in a parallel distributed grid environment. We also compare the performance of MinEX with that of METIS, a popular multilevel family of partitioners, using simulated heterogeneous grid configurations. A solver for the classical N-body problem is implemented to provide a framework for the comparisons. Experimental results show that the proposed MinEX partitioner provides superior quality partitions while being competitive to METIS in terms of execution speed.

The minimum α-small partition problem is the problem of partitioning a given simple polygon into subpolygons, each with diameter at most α, for a given α > 0. This paper considers the version of this problem that disallows Steiner points. This problem is motivated by applications in mesh generation and collision detection. The main result in the paper is a polynomial-time algorithm that solves this problem, and either returns an optimal partition or reports the nonexistence of such a partition. This result contrasts with the recent NP-completeness result for the minimum α-small partition problem for polygons with holes (C. Worman, 15th Canadian Conference on Computational Geometry, 2003). Even though the running time of our algorithm is a polynomial in the input size, it is prohibitive for most real applications and we seek faster algorithms that approximate an optimal solution. We first present a faster 2-approximation algorithm for the problem for simple polygons and then a near linear-time algorithm for convex polygons that produces, for any e > 0, an (α+e)-small partition with no more polygons than in an optimal α-small partition. We also present an exact polynomial-time algorithm for the minimum α-small partition problem with the additional constraint that each piece in the partition be convex.

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.

This issue is dedicated to a selection of papers from the the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), held during September 4–6, 2013, in Sophia Antipolis, France, as part of the annual ALGO meeting. Nine papers were submitted to this special issue and went through the standard refereeing process of Algorithmica. The paper “On Subexponential and FPT-time Inapproximability” by Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos provides new insights into the question of whether the Independent Set problem would be better approximable once endowed with subexponential-time or FPT-time. The paper “Multiparameter analysis for local graph partitioning problems: using greediness for parameterization” by Edouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, and Emeric Tourniaire develops the new algorithmic technique of “greediness for parameterization”which applies to local graph partitioning problems. The paper “Incompressibility of H -Free Edge Modification Problems” by Leizhen Cai and Yufei Cai studies the kernel complexity of problems that ask whether one can add or delete k edges from a given graph so that the graph does not contain a fixed graph H as an induced subgraph. The paper “On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness” by Michael Elberfeld, Christoph Johannes Stockhusen, and Till Tantau shows that various natural problems lie in and may even be complete for different parameterized space classes which leads to new insights into the complexity of the considered problems. The paper “Speeding Up Dynamic Programming with Representative Sets—An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions” by Stefan Fafianie, Hans L. Bodlaender, and Jesper Nederlof provides an experimental evaluation of the technique of representative sets for the

The potential of Boltzmann machines to cope with difficult combinatorial optimization problems is investigated. A discussion of various (parallel) models of Boltzmann machines is given based on the theory of Markov chains. A general strategy is presented for solving (approximately) combinatorial optimization problems with a Boltzmann machine. The strategy is illustrated by discussing the details for two different problems, namely MATCHING and GRAPH PARTITIONING.

This special issue is dedicated to the themes of Algorithms and Computation. The eight papers in this issue cover a wide range of areas within the themes such as graph partitioning, graph matching, graph coloring, tree partitioning, graph minor theory, polynomial multiplication, algorithmic self-assembly, and the complexity of counting problems. The paper “Beyond good partition shapes: an analysis of diffusive graph partitioning” by Meyerhenke and Sauerwald (doi:10.1007/s00453-012-9666-y) studies the problem of graph partitioning and gives a theoretical analysis of the diffusionbased partitioning heuristic Bubble-FOS/C which yields good experimental results in practice. In the paper “Improved algorithms for even factors and square-free simple bmatchings” (doi:10.1007/s00453-012-9642-6), Babenko considers the problem of finding an even factor of maximum cardinality, which is a generalization of path matchings. He gives an improved algorithm to find a maximum cardinality even factor in an odd-cycle symmetric digraph. The paper “3-coloring AT-free graphs in polynomial time” by Stacho (doi:10.1007/ s00453-012-9624-8) deals with graph coloring and gives a polynomial time algorithm for the 3-coloring problem of asteroidal-triple-free graphs. In “Minimum cost partitions of trees with supply and demand” (doi:10.1007/ s00453-011-9573-7), Ito, Hara, Zhou and Nishizeki consider the problem of parti