| 1. |
- Achilleos, Antonis, et al.
(författare)
-
Parameterized Modal Satisfiability
- 2012
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 64:1, s. 38-55
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem’s combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time’s dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose pos- sible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.
|
|
| 2. |
- Albert, Michael, et al.
(författare)
-
Embedding Small Digraphs and Permutations in Binary Trees and Split Trees
- 2020
-
Ingår i: Algorithmica. - : SPRINGER. - 0178-4617 .- 1432-0541. ; 82:3, s. 589-615
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees (Cai et al. in Combin Probab Comput 28(3):335-364, 2019). We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye (SIAM J Comput 28(2):409-432, 1998. 10.1137/s0097539795283954). Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree, with probability tending to one as the number of balls increases, the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.
|
|
| 3. |
- Ashvinkumar, Vikrant, et al.
(författare)
-
Local Routing in Sparse and Lightweight Geometric Graphs
- 2022
-
Ingår i: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 84, s. 1316-1340
-
Tidskriftsartikel (refereegranskat)abstract
- Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O (1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937-951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega (n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O (1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O (1)-competitive routing strategy.
|
|
| 4. |
- Austrin, Per, 1981-, et al.
(författare)
-
On the Impossibility of Cryptography with Tamperable Randomness
- 2017
-
Ingår i: Algorithmica. - : SPRINGER. - 0178-4617 .- 1432-0541. ; 79:4, s. 1052-1101
-
Tidskriftsartikel (refereegranskat)abstract
- We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may efficiently tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. Our main result is a strong negative result: We show that any secure encryption scheme, bit commitment scheme, or zero-knowledge protocol can be "broken" with advantage Omega(p) by a p-tampering attacker. The core of this result is a new algorithm for biasing the output of bounded-value functions, which may be of independent interest. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (1/poly(n))-tampering attacks where n is the security parameter.
|
|
| 5. |
- Bansal, Nikhil, et al.
(författare)
-
New Tools and Connections for Exponential-Time Approximation
- 2019
-
Ingår i: Algorithmica. - : SPRINGER. - 0178-4617 .- 1432-0541. ; 81:10, s. 3993-4009
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1, and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of 1. r for maximum independent set in O*(exp((O) over tilde (n/r log(2) r + r log(2) r))) time, 2. r for chromatic number in O*(exp((O) over tilde (n/r log r + r log(2) r))) time, 3. (2 - 1/r) for minimum vertex cover in O*(exp(n/r(Omega(r)))) time, and 4. (k - 1/r) for minimum k-hypergraph vertex cover in O*(exp(n/(kr)(Omega(kr)))) time. (Throughout, (O) over tilde and O* omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O*(2n/r) (Bourgeois et al. in Discret Appl Math 159(17): 1954-1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp(n(1-o(1))/r(1+o(1))) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370-379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O*(2n/r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP (Chan in J. ACM 63(3): 27: 1-27: 32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23: 128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).
|
|
| 6. |
- Bengtsson, Fredrik, et al.
(författare)
-
Efficient algorithms for k maximum sums
- 2006
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 46:1, s. 27-41
-
Tidskriftsartikel (refereegranskat)abstract
- We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers {x1,x2,...,xn} and an integer parameter k, 1 ≤ k ≤ 1/2n(n-1),the problem involves finding the k largest values of ∑ℓ=ijxℓ for 1 ≤ i ≤ j ≤ n.The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a Θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in O(min {k+nlog2n,n√k} ) time in the worst case. Our algorithm is optimal for k = Ω(n log 2 n) and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.
|
|
| 7. |
- Bhangale, Amey, et al.
(författare)
-
Max-3-Lin Over Non-abelian Groups with Universal Factor Graphs
- 2023
-
Ingår i: Algorithmica. - : Springer Nature. - 0178-4617 .- 1432-0541. ; 85:9, s. 2693-2734
-
Tidskriftsartikel (refereegranskat)abstract
- The factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in which constraints. Thus, an instance of a CSP is completely determined by its factor graph and the list of predicates. We show optimal inapproximability of Max-3-LIN over non-Abelian groups (both in the perfect completeness case and in the imperfect completeness case), even when the factor graph is fixed. Previous reductions which proved similar optimal inapproximability results produced factor graphs that were dependent on the input instance. Along the way, we also show that these optimal hardness results hold even when we restrict the linear equations in the Max-3-LIN instances to the form x· y· z= g, where x, y, z are the variables and g is a group element. We use representation theory and Fourier analysis over non-Abelian groups to analyze the reductions.
|
|
| 8. |
- Bhatt, Mehul, Professor, 1980-, et al.
(författare)
-
MOVE : A Distributed Framework for Materialized Ontology View Extraction
- 2006
-
Ingår i: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 45:3, s. 457-481
-
Tidskriftsartikel (refereegranskat)abstract
- The use of ontologies lies at the very heart of the newly emerging era of semantic web. Ontologies provide a shared conceptualization of some domain that may be communicated between people and application systems. As information on the web increases significantly in size, web ontologies also tend to grow bigger, to such an extent that they become too large to be used in their entirety by any single application. Moreover, because of the size of the original ontology, the process of repeatedly iterating the millions of nodes and relationships to form an optimized sub-ontology becomes very computationally extensive. Therefore, it is imperative that parallel and distributed computing techniques be utilized to implement the extraction process. These problems have stimulated our work in the area of sub-ontology extraction where each user may extract optimized sub-ontologies from an existing base ontology. The extraction process consists of a number of independent optimization schemes that cover various aspects of the optimization process, such as ensuring consistency of the user-specified requirements for the sub-ontology, ensuring semantic completeness of the sub-ontology, etc. Sub-ontologies are valid independent ontologies, known as materialized ontologies, that are specifically extracted to meet certain needs. Our proposed and implemented framework for the extraction process, referred to as Materialized Ontology View Extractor (MOVE), has addressed this problem by proposing a distributed architecture for the extraction/optimization of a sub-ontology from a large-scale base ontology. We utilize coarse-grained data-level parallelism inherent in the problem domain. Such an architecture serves two purposes: (a) facilitates the utilization of a cluster environment typical in business organizations, which is in line with our envisaged application of the proposed system, and (b) enhances the performance of the computationally extensive extraction process when dealing with massively sized realistic ontologies. As ontologies are currently widely used, our proposed approach for distributed ontology extraction will play an important role in improving the efficiency of ontology-based information retrieval.
|
|
| 9. |
- Bilò, Davide, et al.
(författare)
-
Reoptimization of the Shortest Common Superstring Problem
- 2011
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 61:2, s. 227-251
-
Tidskriftsartikel (refereegranskat)abstract
- A reoptimization problem describes the following scenario: given aninstance of an optimization problem together with an optimal solution forit, we want to find a good solution for a locally modified instance. In this paper, we deal with reoptimization variants of the shortest commonsuperstring problem (SCS) where the local modifications consist of adding orremoving a single string. We show the NP-hardness of thesereoptimization problems and design several approximation algorithms forthem. First, we use a technique of iteratively using any SCS algorithm todesign an approximation algorithm for the reoptimization variant of addinga string whose approximation ratio is arbitrarily close to 8/5 andanother algorithm for deleting a string with a ratio tending to 13/7. Bothalgorithms significantly improve over the best currently known SCSapproximation ratio of 2.5. Additionally, this iteration technique can be usedto design an improved SCS approximation algorithm (without reoptimization)if the input instance contains a long string, which might be of independentinterest. However, these iterative algorithms are relatively slow. Thus,we present another, faster approximation algorithm for inserting a stringwhich is based on cutting the given optimal solution and achieves anapproximation ratio of 11/6. Moreover, we give some lower bounds onthe approximation ratio which can be achieved by algorithms that use suchcutting strategies.
|
|
| 10. |
- Björklund, Andreas, et al.
(författare)
-
Constrained Multilinear Detection and Generalized Graph Motifs
- 2016
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 74:2, s. 947-967
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed to have coefficients from a field of characteristic two. As applications of the technique, we show an O^∗(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute Graph Motif, and Min-Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an O^∗((2−ϵ)^k)-time algorithm for the Graph Motif problem implies an O((2−ϵ′)^n)-time algorithm for Set Cover.
|
|
