Nate Veldt, Christine Klymko, David Gleich
2018-11-29
Flow-based methods for local graph clustering have received significant recent attention for their theoretical cut improvement and runtime guarantees. In this work we present two improvements for using flow-based methods in real-world semi-supervised clustering problems. Our first contribution is a generalized objective function that allows practitioners to place strict and soft penalties on excluding specific seed nodes from the output set. This feature allows us to avoid the tendency, often exhibited by previous flow-based methods, to contract a large seed set into a small set of nodes that does not contain all or even most of the seed nodes. Our second contribution is a fast algorithm for minimizing our generalized objective function, based on a variant of the push-relabel algorithm for computing preflows. We make our approach very fast in practice by implementing a global relabeling heuristic and employing a warm-start procedure to quickly solve related cut problems. In practice our algorithm is faster than previous related flow-based methods, and is also more robust in detecting ground truth target regions in a graph, thanks to its ability to better incorporate semi-supervised information about target clusters.
Nathaniel Lahn, Sharath Raghvendra
2019-03-25
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartite graph
with edge weights of or . Let be an upper bound on the weight of any matching in . Consider the subgraph induced by all the edges of with a weight . Suppose every connected component in this subgraph has vertices and edges. We present an algorithm to compute a maximum cardinality matching in in time. When all the edge weights are (symmetrically when all weights are ), our algorithm will be identical to the well-known Hopcroft-Karp (HK) algorithm, which runs in time. However, if we can carefully assign weights of and on its edges such that both and are sub-linear in and for , then we can compute maximum cardinality matching in in time. Using our algorithm, we obtain a new time algorithm to compute an -approximate bottleneck matching of and an time algorithm for computing -approximate bottleneck matching in -dimensions. All previous algorithms take time. Given any graph that has an easily computable balanced vertex separator for every subgraph of size , for , we can apply our algorithm to compute a maximum matching in time improving upon the time taken by the HK-Algorithm.
Jordi Bataller Mascarell
2019-03-25
In this paper, we introduce two algorithms that solve the mutual exclusion problem for concurrent processes that communicate through shared variables, [2]. Our algorithms guarantee that any process trying to enter the critical section, eventually, does enter it. They are formally proven to be correct. The first algorithm uses a special coordinator process in order to ensure equal chances to processes waiting for the critical section. In the second algorithm, with no coordinator, the process exiting the critical section is in charge to fairly elect the following one. In the case that no process is waiting, the turn is marked free and will be determined by future waiting processes. The type of shared variables used are a turn variable, readable and writable by all processes; and a flag array, readable by all with flag[i] writable only by process i. There is a version of the first algorithm where no writable by all variable is used. The bibliography reviewed for this paper is [4] and [3], all the rest is original work.
Oscar Defrain, Lhouari Nourine
2019-01-22
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we show that this result holds even when the premises in the implicational base are of size at most two. In the case of premises of size one---when the lattice is distributive---we show that the dualization is possible in output quasi-polynomial time whenever the graph of implications is of bounded maximum induced matching. Lattices that share this property include distributive lattices coded by the ideals of an interval order.
Ortho Flint, Asanka Wickramasinghe, Jason Brasse, Christopher Fowler
2019-03-24
In this paper, we provide a polynomial time (and space), algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies.
Zhonghua Han, Jingyuan Zhang, Xiaoting Dong, Yuanwei Qi
2019-03-11
Aiming at solving the problem that the moving route is complicated and the scheduling is difficult in the routing buffer of the bus in the manufacturing workshop, a routing buffer mathematical programming model for bus manufacturing workshop is proposed. We design a moving approach for minimizing the total setup cost for moving in routing buffer. The framework and the solution ofthe optimization problem of such a bus manufacturing workshop scheduling with routing buffer arepresented. The evaluation results show that, comparing with the irregularly guided moving method, the proposed method can better guide the bus movement in routing buffer by reducing the total setup time of all buses processed at the next stage, and obtaining a better scheduling optimization solution with minimize maximum total completion time.
Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins
2018-11-28
We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to the algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version and use it as a subroutine to solve the latter.
Kristóf Bérczi, Endre Boros, Ondřej Čepek, Petr Kučera, Kazuhisa Makino
2018-11-13
Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard.
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer
2019-03-01
We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the searcher learns of all neighboring vertices and the connecting edge weights. The goal such an exploration is to minimize its total cost, where each edge traversal incurs a cost of the corresponding edge weight. We investigate the problem on tadpole graphs (also known as dragons, kites), which consist of a cycle with an attached path. Miyazaki et al. (The online graph exploration problem on restricted graphs, IEICE Transactions 92-D (9), 2009) showed that every online algorithm on these graphs must have a competitive ratio of 2-epsilon, but did not provide upper bounds for non-unit edge weights. We show via amortized analysis that a greedy approach yields a matching competitive ratio of 2 on tadpole graphs, for arbitrary non-negative edge weights.
Pankaj K. Agarwal, Hsien-Chih Chang, Allen Xiao
2019-03-22
Let
and be two point sets in the plane of sizes and respectively (assume ), and let be a parameter. A matching between and is a family of pairs in so that any point of appears in at most one pair. Given two positive integers and , we define the cost of matching to be where is the -norm. The geometric partial matching problem asks to find the minimum-cost size- matching between and . We present efficient algorithms for geometric partial matching problem that work for any powers of -norm matching objective: An exact algorithm that runs in time, and a -approximation algorithm that runs in time. Both algorithms are based on the primal-dual flow augmentation scheme; the main improvements involve using dynamic data structures to achieve efficient flow augmentations. With similar techniques, we give an exact algorithm for the planar transportation problem running in time.
