Data Structures And Algorithms

---

Variance Reduction for Matrix Games (1907.02056v1)

Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian

2019-07-03

We present a randomized primal-dual algorithm that solves the problem to additive error in time , for matrix with larger dimension and nonzero entries. This improves on Nemirovski's mirror-prox method by a factor of and is faster than stochastic gradient methods in the accurate and/or sparse regime . Our results hold for in the simplex (matrix games, linear programming) and for in an ball and in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines the mirror-prox method and a novel variance-reduced gradient estimator based on "sampling from the difference" between the current iterate and a reference point.

Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm (1907.02053v1)

Lars Gottesbüren, Michael Hamann, Dorothea Wagner

2019-07-03

In this paper, we propose HyperFlowCutter, an algorithm for balanced hypergraph bipartitioning. It is based on minimum S-T hyperedge cuts and maximum flows. It computes a sequence of bipartitions that optimize cut size and balance in the Pareto sense, being able to trade one for the other. HyperFlowCutter builds on the FlowCutter algorithm for partitioning graphs. We propose additional features, such as handling disconnected hypergraphs, novel methods for obtaining starting S,T pairs as well as an approach to refine a given partition with HyperFlowCutter. Our main contribution is ReBaHFC, a new algorithm which obtains an initial partition with the fast multilevel hypergraph partitioner PaToH and then improves it using HyperFlowCutter as a refinement algorithm. ReBaHFC is able to significantly improve the solution quality of PaToH at little additional running time. The solution quality is only marginally worse than that of the best-performing hypergraph partitioners KaHyPar and hMETIS, while being one order of magnitude faster. Thus ReBaHFC offers a new time-quality trade-off in the current spectrum of hypergraph partitioners. For the special case of perfectly balanced bipartitioning, only the much slower plain HyperFlowCutter yields slightly better solutions than ReBaHFC, while only PaToH is faster than ReBaHFC.

Finding Minimum Spanning Forests in a Graph (1705.00774v2)

Abdel-Rahman Madkour, Phillip Nadolny, Matthew Wright

2017-05-02

We introduce a graph partitioning problem motivated by computational topology and propose two algorithms that produce approximate solutions. Specifically, given a weighted, undirected graph and a positive integer , we desire to find disjoint trees within such that each vertex of is contained in one of the trees and the weight of the largest tree is as small as possible. We are unable to find this problem in the graph partitioning literature, but we show that the problem is NP-complete. We then propose two approximation algorithms, one that uses a spectral clustering approach and another that employs a dynamic programming strategy, which produce near-optimal partitions on a family of test graphs. We describe these algorithms and analyze their empirical performance.

Bilu-Linial stability, certified algorithms and the Independent Set problem (1810.08414v2)

Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan

2018-10-19

We study the Maximum Independent Set (MIS) problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of MIS is -stable if it has a unique optimal solution that remains the unique optimum under multiplicative perturbations of the weights by a factor of at most . The goal then is to efficiently recover the unique optimal solution. In this work, we solve stable instances of MIS on several graphs classes: we solve -stable instances on graphs of maximum degree , -stable instances on -colorable graphs and -stable instances on planar graphs. For general graphs, we present a strong lower bound showing that there are no efficient algorithms for -stable instances of MIS, assuming the planted clique conjecture. We also give an algorithm for -stable instances. As a by-product of our techniques, we give algorithms and lower bounds for stable instances of Node Multiway Cut. Furthermore, we prove a general result showing that the integrality gap of convex relaxations of several maximization problems reduces dramatically on stable instances. Moreover, we initiate the study of certified algorithms, a notion recently introduced by Makarychev and Makarychev (2018), which is a class of -approximation algorithms that satisfy one crucial property: the solution returned is optimal for a perturbation of the original instance. We obtain -certified algorithms for MIS on graphs of maximum degree , and -certified algorithms on planar graphs. Finally, we analyze the algorithm of Berman and Furer (1994) and prove that it is a -certified algorithm for MIS on graphs of maximum degree where all weights are equal to 1.

Equal-Subset-Sum Faster Than the Meet-in-the-Middle (1905.02424v2)

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki

2019-05-07

In the Equal-Subset-Sum problem, we are given a set of integers and the problem is to decide if there exist two disjoint nonempty subsets , whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in time and polynomial space.

Proportionally dense subgraph of maximum size: complexity and approximation (1903.06579v4)

Cristina Bazgan, Janka Chlebíková, Clément Dallard, Thomas Pontoizeau

2019-03-15

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time -approximation algorithm for the problem, where is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with vertices (except two) have a PDS of size , which we prove to be an upper bound on the size of a PDS in cubic graphs.

Circular Pattern Matching with Mismatches (1907.01815v1)

Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

2019-07-03

The -mismatch problem consists in computing the Hamming distance between a pattern of length and every length- substring of a text of length , if this distance is no more than . In many real-world applications, any cyclic shift of is a relevant pattern, and thus one is interested in computing the minimal distance of every length- substring of and any cyclic shift of . This is the circular pattern matching with mismatches (-CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the -CPM problem. Specifically, we show an -time algorithm and an -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the -mismatch problem [Bringmann et al., SODA 2019].

Accelerating Deconvolution on Unmodified CNN Accelerators for Generative Adversarial Networks -- A Software Approach (1907.01773v1)

Kaijie Tu

2019-07-03

Generative Adversarial Networks (GANs) are the emerging machine learning technology that can learn to automatically create labeled datasets in massive application domains such as speech, image, video and texts. A GAN typically includes a generative model that is taught to generate any distribution of data, and a discriminator trained to distinguish the synthetic data from real-world data. Both convolutional and deconvolutional layers are the major source of performance overhead for GANs and directly impacts the efficiency of GAN-based systems. There are many prior works investigating specialized hardware architectures that can accelerate convolution and deconvolution simultaneously, but they entail intensive hardware modifications to the existing CNN accelerators or processors that focus on convolution acceleration. In contrast, this work proposes a novel deconvolution layer implementation with a software approach and enables fast and efficient generative network inference on the legacy Convolutional Neural Networks (CNNs) accelerators. Our proposed method reorganizes the computation of deconvolutional layer and allows the CNN accelerators to treat it as the standard convolutional layer after we split the original deconvolutional filters into multiple small filters. The proposed data flow is implemented on representative CNN accelerators including dot-production array and regular 2D PE array architectures. Compared to the prior baseline acceleration scheme, the implemented acceleration scheme achieves 2.4X - 4.3X performance speedup and reduces the energy consumption by 27.7% - 54.5% on a set of realistic benchmarks.

Algorithms for Competitive Division of Chores (1907.01766v1)

Simina Brânzei, Fedor Sandomirskiy

2019-07-03

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).

Generalized Assignment via Submodular Optimization with Reserved Capacity (1907.01745v1)

Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai

2019-07-03

We study a variant of the \emph{generalized assignment problem} ({\sf GAP}) with group constraints. An instance of {\sf Group GAP} is a set of items, partitioned into groups, and a set of uniform (unit-sized) bins. Each item has a size , and a profit if packed in bin . A group of items is \emph{satisfied} if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of {\sf Group GAP} in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a -approximation algorithm for {\sf Group GAP} instances where the total size of each group is at most . At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of {\sf GAP}, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is \emph{reserved} for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack \emph{with reserved capacity} constraint may find applications in solving other group assignment problems.

---