323,025 research outputs found
A new strategy for querying priced information.
No full textCicalese F, Laber ES. A new strategy for querying priced information. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005). 2005: 674-683
Approximating the maximum consecutive subsums of a sequence
No full textWe present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ(n2) procedure. We show how to construct a (1+ε)-approximate index for all Parikh vectors of a binary string in O(nlog^2n/log(1+ε), for any constant ε>0.
Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time
Improved Approximation Algorithms for the Average-Case Tree Searching Problem
No full textWe study the following tree search problem: in a given tree T = (V , E) a vertex has been marked and we want to identify it. In order to locate the marked vertex, we can use edge queries. An edge query e asks in which of the two connected components of T \ e the marked vertex lies. The worst-case scenario where one is interested in minimizing the maximum number of queries is well understood, and linear time algorithms are known for finding an optimal search strategy. Here we study the more involved average-case analysis: A function w : V → R+ is given which measures the likelihood for a vertex to be the one marked, and we seek to determine the strategy (decision tree) that minimizes the weighted average number of queries.
In a companion paper we prove that the above tree search problem is NP- complete even for the class of trees of bounded diameter or bounded degree. Here, we match this complexity result with a tight algorithmic analysis of the bounded degree instances. We show that any optimal strategy (i.e., one that minimizes the weighted average number of queries) performs at most O(Delta(T )(log |V | + log(w(T )/wmin))) queries in the worst case, where w(T ) is the sum of the likelihoods of the vertices of T , wmin is the minimum positive likelihood over the vertices of T and Delta(T ) is the maximum degree of T . We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree. We also show that for unbounded instances a natural greedy strategy attains a 1.62-approximation, improv- ing upon the best known 14-approximation guarantee, previously provided by two of the authors
On the star decomposition of a graph: Hardness results and approximation for the max{\textendash}min optimization problem
No full textWe study the problem of decomposing a graph into stars so that the minimum size star in the decomposition is as large as possible. Problems of graph decomposition have been actively investigated since the 70's. The question we consider here also combines the structure of a facility location problem (choosing the centres of the stars) with a max-min fairness optimization criterion that has recently received attention in resource allocation problems, e.g., the Santa Claus problem.We focus on computational and algorithmic questions: We show that the problem is hard even in the case of planar graphs of maximum degree not larger than four, and already for decompositions into stars of size at least three. We are able to tightly characterize the boundaries between efficiently solvable instances and hard ones: we show that relaxing any of the conditions in our hardness result (minimum size of the stars or degree of the input graph) makes the problem polynomially solvable.Our complexity result implies also the APX hardness of the problem ruling out any approximation guarantee better than 2/3. We complement this inapproximability result with a 1/2-approximation algorithm. Finally, we give a polynomial time algorithm for trees. A nice property of our algorithms is that they can all be implemented to run in time linear in the size of the input graph. (C) 2020 Published by Elsevier B.V
On lower bounds for the Maximum Consecutive Subsums Problem and the (min, +)-convolution
No full textGiven a sequence of n numbers, the MAXIMUM CONSECUTIVE SUBSUMS PROBLEM (MCSP) asks for the maximum consecutive sum of lengths l for each l = 1, ..., n. No algorithm is known for this problem which is significantly better than the naive quadratic solution. Nor a super linear lower bound is known. The best known bound for the MCSP is based on the the computation of the (min; +)-convolution, another problem for which neither an O(n2-ε) upper bound is known nor a super linear lower bound. We show that the two problems are in fact computationally equivalent by providing linear reductions between them. Then, we concentrate on the problem of finding super linear lower bounds and provide empirical evidence for our conjecture that the solution of both problems requires Ω(n log n) time in the decision tree model
Function Evaluation: decision trees optimizing simultaneously worst and expected testing cost
No full textIn several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete func- tion by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the cor- responding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the pos- sible variables’ assignments).Our algorithm builds a strategy (decision tree) which attains a logarithmic approximation simultaneously for the expected and worst cost spent. This is best possible since, under stan- dard complexity assumption, no algorithm that can guarantee o(log n) approximation
Decision Trees with Short Explainable Rules
No full textDecision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explainability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our new measure (which we call the explanation size) and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees O(ln n)-approximation (hence optimal if P ≠ NP) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations
Diffusive author(s), cohesive author: Analysis of S/N (1994)
No full textThis study indicates the ways in which various aspects of the author(s) are brought forth in Dumb type’s performance art, the S/N production. Previous research has suggested a non-hierarchical organization of Dumb type and the absence of a “privileged author” in Dumb type’s collaborative work, S/N. However, the results that I have investigated from member’s interviews on the creative process of S/N along with my analysis of the recorded images of S/N, indicate a different aspect of the author(s). First, S/N was created through, so to speak, the collective ideas of the members of Dumb type. Further, S/N has at least nine quotations from previous performances, installations, and printed writings, besides the work-in-progress technique. Explicating one of the “author functions” as given by Michel Foucault, each text has plural subjects of the author. However, it has been revealed from members’ interviews that Teiji Furuhashi had a decision-making role in selecting the members’ ideas within the performance. Since then, S/N has had plural subjects of creation; however, Furuhashi is one of the subjects of creation along with the “privileged author.” S/N has plural authors (diffusive authors) yet at the same time, it has a “privileged author,” Teiji Furuhashi (cohesive author)
Teaching with limited information on the Learner's behaviour
No full textMachine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al., ICML 2019], where the teaching is done interactively without having any knowledge of the Learner's algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis h∗. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that h∗ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of h∗. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
