Data Structures And Algorithms | 2019-07-05
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
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
-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
-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
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
, 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
, 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
of length
and every length-
of length
-time algorithm and an
-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the
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
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.