Name
Abstract | ||
|---|---|---|
Given a permutation group G ≤ Sn by a generating set, we explore MWP (the minimum weight problem) and SDP (the subgroup distance problem) for some natural metrics on permutations. These problems are know to be NP-hard. We study both exact and approximation versions of these problems. We summarize our main results: - For our upper bound results we focus on the Hamming and the l∞ permutation metrics. For the l∞ metric, we give a randomized 2O(n) time algorithm for finding an optimal solution to MWP. Interestingly, this algorithm adapts ideas from the Ajtai-Kumar-Sivakumar algorithm for the shortest vector problem in lattices [AKS01]. For the Hamming metric, we again give a 2O(n) time algorithm for finding an optimal solution to MWP. This algorithm is based on the classical Schrier-Sims algorithm for finding pointwise stabilizer subgroups of permutation groups. - It is known that SDP is NP-hard([BCW06]) and it easily follows that SDP is hard to approximate within a factor of logO(1) n unless P = NP. In contrast, we show that SDP for approximation factor more than n/ log n is not NP-hard unless there is an unlikely containment of complexity classes. - For several permutation metrics, we show that the minimum weight problem is polynomial-time reducible to the subgroup distance problem for solvable permutation groups. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-77566-9_12 | SOFSEM |
Keywords | Field | DocType |
minimum weight problem,optimal solution,shortest vector problem,ajtai-kumar-sivakumar algorithm,algorithm adapts idea,subgroup distance problem,permutation group,time algorithm,permutation metrics,classical schrier-sims algorithm,algorithmic problem,upper bound,polynomial time,abelian group,complexity class | Permutation graph,Discrete mathematics,Combinatorics,Permutation,Cyclic permutation,Permutation group,Random permutation,Bit-reversal permutation,Generalized permutation matrix,Partial permutation,Mathematics | Conference |
Volume | ISSN | ISBN |
4910 | 0302-9743 | 3-540-77565-X |
Citations | PageRank | References |
2 | 0.39 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| Pushkar S. Joglekar | 2 | 35 | 5.69 |