Search

We give a 2-approximation algorithm for Cluster Vertex Deletion. This tight result matches the hardness lower bound. We obtain a new deterministic 7/3-approximation algorithm for Feedback Vertex Set in Tournaments. This result is based on the LP given by just one round of Sherali-Adams. We find a new, simpler deterministic (2 + epsilon)-approximation algorithm for Split Vertex Deletion. We give a 2-approximation algorithm for Claw-Free Vertex Deletion in triangle-free graphs. In the case of general graphs we prove that it is UGC-hard to obtain an approximation ratio lower than 3., Doctorat en Sciences, info:eu-repo/semantics/nonPublished

© 2018, Springer International Publishing AG, part of Springer Nature. We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE -completeness of the following decision problems: Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable “flips” (assignment changes), preserving satisfiability at every step?Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum?Given two points in {0,1}n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.

The modular subset sum problem consists of deciding, given a modulus m, a multiset S of n integers in 0.m – 1, and a target integer t, whether there exists a subset of S with elements summing to t (mod m), and to report such a set if it exists. We give a simple O(m log m)-time with high probability (w.h.p.) algorithm for the modular subset sum problem. This builds on and improves on a previous O(m log7 m) w.h.p. algorithm from Axiotis, Backurs, Jin, Tzamos, and Wu (SODA 19). Our method utilizes the ADT of the dynamic strings structure of Gawrychowski et al. (SODA 18). However, as this structure is rather complicated we present a much simpler alternative which we call the Data Dependent Tree. As an application, we consider the computational version of a fundamental theorem in zero-sum Ramsey theory. The Erdős-Ginzburg-Ziv Theorem states that a multiset of 2n – 1 integers always contains a subset of cardinality exactly n whose values sum to a multiple of n. We give an algorithm for finding such a subset in time O(n log n) w.h.p. which improves on an O(n2) algorithm due to Del Lungo, Marini, and Mori (Disc. Math. 09)., info:eu-repo/semantics/published

The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set S of n points in ℝ^d, a point y∈ ℝ^d, and an integer 2 ≤ k ≤ d, find an affine combination of at most k points of S that is nearest to y. We describe a O(n^{k-1} log^{d-k+2} n)-time randomized (1+ε)-approximation algorithm for this problem with d and ε constant. This is the first algorithm for this problem running in time o(n^k). Its running time is similar to the query time of a data structure recently proposed by Har-Peled, Indyk, and Mahabadi (ICALP'18), while not requiring any preprocessing. Up to polylogarithmic factors, it matches a conditional lower bound relying on a conjecture about affine degeneracy testing. In the special case where k = d = O(1), we provide a simple O_δ(n^{d-1+δ})-time deterministic exact algorithm, for any δ > 0. Finally, we show how to adapt the approximation algorithm for the sparse linear regression and sparse convex regression problems with the same running time, up to polylogarithmic factors.

We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned squares in the plane and axis-aligned d-dimensional hypercubes.It is known that a maximum independent set of a collection of n intervals can be found in O(nlogn) time, while it is already \textsf{NP}-hard for a set of unit squares. Moreover, the problem is inapproximable on many important graph families, but admits a \textsf{PTAS} for a set of arbitrary pseudo-disks. Therefore, a fundamental question in computational geometry is whether it is possible to maintain an approximate maximum independent set in a set of dynamic geometric objects, in truly sublinear time per insertion or deletion. In this work, we answer this question in the affirmative for intervals, squares and hypercubes.First, we show that for intervals a (1+ε)-approximate maximum independent set can be maintained with logarithmic worst-case update time. This is achieved by maintaining a locally optimal solution using a constant number of constant-size exchanges per update.We then show how our interval structure can be used to design a data structure for maintaining an expected constant factor approximate maximum independent set of axis-aligned squares in the plane, with polylogarithmic amortized update time. Our approach generalizes to d-dimensional hypercubes, providing a O(4d)-approximation with polylogarithmic update time.Those are the first approximation algorithms for any set of dynamic arbitrary size geometric objects; previous results required bounded size ratios to obtain polylogarithmic update time. Furthermore, it is known that our results for squares (and hypercubes) cannot be improved to a (1+ε)-approximation with the same update time., info:eu-repo/semantics/published

The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set S of n points in ?^d, a point y? ?^d, and an integer 2 ? k ? d, find an affine combination of at most k points of S that is nearest to y. We describe a O(n^{k-1} log^{d-k+2} n)-time randomized (1+?)-approximation algorithm for this problem with d and ? constant. This is the first algorithm for this problem running in time o(n^k). Its running time is similar to the query time of a data structure recently proposed by Har-Peled, Indyk, and Mahabadi (ICALP'18), while not requiring any preprocessing. Up to polylogarithmic factors, it matches a conditional lower bound relying on a conjecture about affine degeneracy testing. In the special case where k = d = O(1), we provide a simple O_?(n^{d-1+?})-time deterministic exact algorithm, for any ? > 0. Finally, we show how to adapt the approximation algorithm for the sparse linear regression and sparse convex regression problems with the same running time, up to polylogarithmic factors.

We prove that some exact geometric pattern matching problems reduce in linear time to o k-SUM when the pattern has a fixed size k. This holds in the real RAM model for searching for a similar copy of a set of k ≥ 3 points within a set of n points in the plane, and for searching for an affine image of a set of k ≥ d+2 points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.

We consider the design of adaptive data structures for searching elements of a tree-structured space.We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings.The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path.We describe an online $O(log log n)$-competitive search tree data structure in this model, matching thebest known competitive ratio of binary search trees.Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths., info:eu-repo/semantics/published