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.
Mary Cryan, Heng Guo, Giorgos Mousa
2019-03-14
We show that the modified log-Sobolev constant for a natural Markov chain which converges to an r-homogeneous strongly log-concave distribution is at least 1/r. As a consequence, we obtain an asymptotically optimal mixing time bound for this chain. Applications include the bases-exchange random walk in a matroid.
Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, Alexander Nover
2019-03-14
Given an edge-weighted graph G on n nodes, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximized. We propose a fixed-parameter tractable algorithm parameterized by the number k of crossings in a given drawing of G. Our algorithm achieves a running time of O(2^k p(n + k)), where p is the polynomial running time for planar Max-Cut. The only previously known similar algorithm [8] is restricted to 1-planar graphs (i.e., at most one crossing per edge) and its dependency on k is of order 3^k . A direct consequence of our result is that Max-Cut is fixed-parameter tractable w.r.t. the crossing number, even without a given drawing.
Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, Dean Leitersdorf
2019-03-14
We design fast deterministic algorithms for distance computation in the congested clique model. Our key contributions include: -- A
-approximation for all-pairs shortest paths in rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. -- A -approximation for multi-source shortest paths from sources in rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in rounds.
Luzhi Wang, Chu-Min Li, Junping Zhou, Bo Jin, Minghao Yin
2019-03-14
This paper proposes a novel branch-and-bound(BMWVC) algorithm to exactly solve the minimum weight vertex cover problem (MWVC) in large graphs. The original contribution is several new graph reduction rules, allowing to reduce a graph G and the time needed to find a minimum weight vertex cover in G. Experiments on large graphs from real-world applications show that the reduction rules are effective and the resulting BMWVC algorithm outperforms relevant exact and heuristic MWVC algorithms.
Marcel Wild
2017-12-03
The model set of a general Boolean function in CNF is calculated in a compressed format, using novel wildcards. This method can be explained in very visual ways. Preliminary comparison with existing methods (BDD's and Mathematica's ESOP command) looks promising but our algorithm begs for a C encoding which would render it comparable in more systematic ways.
Palash Dey, Sourav Medya
2019-03-14
Covert networks are social networks that often consist of harmful users. Social Network Analysis (SNA) has played an important role in reducing criminal activities (e.g., counter terrorism) via detecting the influential users in such networks. There are various popular measures to quantify how influential or central any vertex is in a network. As expected, strategic and influential miscreants in covert networks would try to hide herself and her partners (called {\em leaders}) from being detected via these measures by introducing new edges. Waniek et al. show that the corresponding computational problem, called Hiding Leader, is NP-Complete for the degree and closeness centrality measures. We study the popular core centrality measure and show that the problem is NP-Complete even when the core centrality of every leader is only
. On the contrary, we prove that the problem becomes polynomial time solvable for the degree centrality measure if the degree of every leader is bounded above by any constant. We then focus on the optimization version of the problem and show that the Hiding Leader problem admits a factor approximation algorithm for the degree centrality measure. We complement it by proving that one cannot hope to have any factor approximation algorithm for any constant unless there is a factor polynomial time algorithm for the Densest -Subgraph problem which would be considered a significant breakthrough.
Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen
2019-01-11
Computing the Strongly-Connected Components (SCCs) in a graph
is known to take only time using an algorithm by Tarjan from 1972[SICOMP 72] where , . For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for \emph{decremental} graphs, i.e. graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time , thus only a polylogarithmic factor from the optimal running time. Previously such a result was only known for the special case of planar graphs [Italiano et al, STOC 2017]. Our result should be compared to the formerly best algorithm for general graphs achieving total update time by Chechik et.al. [FOCS 16] which improved upon a breakthrough result leading to total update time by Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]; these results in turn improved upon the longstanding bound of by Roditty and Zwick [STOC 04]. All of the above results also apply to the decremental Single-Source Reachability (SSR) problem, which can be reduced to decrementally maintaining SCCs. A bound of total update time for decremental SSR was established already in 1981 by Even and Shiloach [JACM 1981]. Using a well known reduction, we can maintain the reachability of pairs , in fully-dynamic graphs with update time and query time for all ; this generalizes an earlier All-Pairs Reachability where [{\L}\k{a}cki, TALG 2013].
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
2011-07-12
A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. We show a linear-time algorithm computing a linear-size representation of all the seeds of a word (the number of seeds might be quadratic). In particular, one can easily derive the shortest seed and the number of seeds from our representation. Thus, we solve an open problem stated in the survey by Smyth (2000) and improve upon a previous O(n log n) algorithm by Iliopoulos, Moore, and Park (1996). Our approach is based on combinatorial relations between seeds and subword complexity (used here for the first time in context of seeds). In the previous papers, the compact representation of seeds consisted of two independent parts operating on the suffix tree of the word and the suffix tree of the reverse of the word, respectively. Our second contribution is a simpler representation of all seeds which avoids dealing with the reversed word. A preliminary version of this work, with a much more complex algorithm constructing the earlier representation of seeds, was presented at the 23rd Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2012).
Adrien Argento, Pierre Charbit, Alantha Newman
2018-08-27
For a graph
and integer , two functions from into are adjacent if for all edges of , . The graph of all such functions is the exponential graph . El-Zahar and Sauer proved that if , then is 3-chromatic. Tardif showed that, implicit in their proof, is an algorithm for 3-coloring whose time complexity is polynomial in the size of . Tardif then asked if there is an "explicit" algorithm for finding such a coloring: Essentially, given a function belonging to a 3-chromatic component of , can we assign a color to this vertex in time polynomial in the size of ? The main result of this paper is to present such an algorithm, answering Tardif's question affirmatively. Our algorithm yields an alternative proof of the theorem of El-Zahar and Sauer that the categorical product of two 4-chromatic graphs is 4-chromatic.
