Pavel S. Ruzankin
2017-01-09
We present a new algorithm which detects the maximal possible number of matched disjoint pairs satisfying a given caliper when a bipartite matching is done with respect to a scalar index (e.g., propensity score), and constructs a corresponding matching. Variable width calipers are compatible with the technique, provided that the width of the caliper is a Lipschitz function of the index. If the observations are ordered with respect to the index then the matching needs
operations, where is the total number of subjects to be matched. The case of 1-to- matching is also considered. We offer also a new fast algorithm for optimal complete one-to-one matching on a scalar index when the treatment and control groups are of the same size. This allows us to improve greedy nearest neighbor matching on a scalar index. Keywords: propensity score matching, nearest neighbor matching, matching with caliper, variable width caliper.
Jose Correa, Raimundo Saona, Bruno Ziliotto
2018-07-19
In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no algorithm for the gambler can achieve better than 0.732.
Adam Kurpisz, Timo de Wolff
2019-03-12
We compare four key hierarchies for solving Constrained Polynomial Optimization Problems (CPOP): Sum of Squares (SOS), Sum of Diagonally Dominant Polynomials (SDSOS), Sum of Nonnegative Circuits (SONC), and the Sherali Adams (SA) hierarchies. We prove a collection of dependencies among these hierarchies both for general CPOPs and for optimization problems on the Boolean hypercube. Key results include for the general case that the SONC and SOS hierarchy are polynomially incomparable, while SDSOS is contained in SONC. A direct consequence is the non-existence of a Putinar-like Positivstellensatz for SDSOS. On the Boolean hypercube, we show as a main result that Schm"udgen-like versions of the hierarchies SDSOS, SONC, and SA* are polynomially equivalent. Moreover, we show that SA* is contained in any Schm"udgen-like hierarchy that provides a O(n) degree bound.
Martin Skrodzki
2019-03-12
For practical applications, any neighborhood concept imposed on a finite point set P is not of any use if it cannot be computed efficiently. Thus, in this paper, we give an introduction to the data structure of k-d trees, first presented by Friedman, Bentley, and Finkel in 1977. After a short introduction to the data structure (Section 1), we turn to the proof of efficiency by Friedman and his colleagues (Section 2). The main contribution of this paper is the translation of the proof of Freedman, Bentley, and Finkel into modern terms and the elaboration of the proof.
Vilnis Liepins
2013-03-08
This summary of the doctoral thesis is created to emphasize the close connection of the proposed spectral analysis method with the Discrete Fourier Transform (DFT), the most extensively studied and frequently used approach in the history of signal processing. It is shown that in a typical application case, where uniform data readings are transformed to the same number of uniformly spaced frequencies, the results of the classical DFT and proposed approach coincide. The difference in performance appears when the length of the DFT is selected to be greater than the length of the data. The DFT solves the unknown data problem by padding readings with zeros up to the length of the DFT, while the proposed Extended DFT (EDFT) deals with this situation in a different way, it uses the Fourier integral transform as a target and optimizes the transform basis in the extended frequency range without putting such restrictions on the time domain. Consequently, the Inverse DFT (IDFT) applied to the result of EDFT returns not only known readings, but also the extrapolated data, where classical DFT is able to give back just zeros, and higher resolution are achieved at frequencies where the data has been successfully extended. It has been demonstrated that EDFT able to process data with missing readings or gaps inside or even nonuniformly distributed data. Thus, EDFT significantly extends the usability of the DFT-based methods, where previously these approaches have been considered as not applicable. The EDFT founds the solution in an iterative way and requires repeated calculations to get the adaptive basis, and this makes it numerical complexity much higher compared to DFT. This disadvantage was a serious problem in the 1990s, when the method has been proposed. Fortunately, since then the power of computers has increased so much that nowadays EDFT application could be considered as a real alternative.
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé
2019-03-12
A hole in a graph is an induced cycle of length at least
, and an antihole is the complement of an induced cycle of length at least . A hole or antihole is long if its length is at least . For an integer , the -prism is the graph consisting of two cliques of size joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no -prism (for any fixed integer ), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length . The algorithms use the framework of minimal chordal completions and potential maximal cliques.
Moses Ganardi, Artur Jeż, Markus Lohrey
2019-02-10
It is shown that a context-free grammar of size
that produces a single string (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for of size , whose unique derivation tree has depth . This solves an open problem in the area of grammar-based compression. Similar results are shown for two formalism for grammar-based tree compression: top dags and forest straight-line programs. These balancing results are all deduced from a single meta theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to with the cost of a constant multiplicative size increase. Here, refers to the size of the unfolding (or unravelling) of the circuit.
Therese Biedl, Philipp Kindermann
2018-12-11
It is well-known that every planar graph has a Tutte path, i.e., a path
such that any component of has at most three attachment points on . However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to . This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, Yihan Sun
2019-03-11
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously, and join up later. The tasks share memory, and costs are measured in terms of work (total number of instructions), and span (longest dependence chain). Due to the asynchronous nature of the model, and a variety schedulers that are efficient in both theory and practice, variants of the model are widely used in practice in languages such as Cilk and Java Fork-Join. PRAM algorithms can be simulated in the model but at a loss of a factor of
so most PRAM algorithms are not optimal in the model even if optimal on the PRAM. All algorithms we describe are optimal in work and span (logarithmic in span). Several are randomized. Beyond being the first optimal algorithms for their problems in the model, most are very simple.
Yi-Jun Chang, Wenzheng Li, Seth Pettie
2017-11-03
Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for
-list coloring in the randomized model running in time, where is the deterministic complexity of -list coloring on -vertex graphs. (In this problem, each has a palette of size .) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [STOC'16, JACM'18] with complexity , and, for some range of , is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [FOCS'16] and Barenboim, Elkin, and Goldenberg [PODC'18], with complexity . Our algorithm "appears to be" optimal, in view of the randomized lower bound due to Chang, Kopelowitz, and Pettie [FOCS'16], where is the deterministic complexity of -list coloring. At present, the best upper bounds on and are both and use a black box application of network decompositions (Panconesi and Srinivasan [Journal of Algorithms'96]). It is quite possible that the true complexities of both problems are the same, asymptotically, which would imply the randomized optimality of our -list coloring algorithm.
