✦ LIBER ✦

Packing and Decomposition Problems for Polynomial Association Schemes

✍ Scribed by V.I. Levenshtein

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 496 KB
Volume: 14
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1993.1049

No coin nor oath required. For personal study only.

✦ Synopsis

We consider (P) - and (Q)-polynomial association schemes and introduce definitions of Delsarte codes and decomposable schemes. Many known combinatorial notions can be defined as Delsarte codes in suitable association schemes, and almost all classical association schemes turn out to be decomposable. For decomposable association schemes we prove some packing bounds, which were proven before only for antipodal schemes. We also prove that any Delsarte code consists of maximal possible numbers of points for its minimal distance. Some statements about the connection between designs in decomposable schemes and designs in their projections are also given. Detailed proofs of some of our results will be published in the longer paper [24], where analogous problems for a wider class of finite and infinite polynomial metric spaces are considered.

📜 SIMILAR VOLUMES

Polynomial time approximation schemes fo

Polynomial time approximation schemes for class-constrained packing problems

✍ Hadas Shachnai; Tami Tamir 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 207 KB

We consider variants of the classic bin packing and multiple knapsack problems, in which sets of items of di erent classes (colours) need to be placed in bins; the items may have di erent sizes and values. Each bin has a limited capacity, and a bound on the number of distinct classes of items it can

Approximation schemes for ordered vector

Approximation schemes for ordered vector packing problems

✍ Alberto Caprara; Hans Kellerer; Ulrich Pferschy 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

Character Products and Q-Polynomial Grou

Character Products and Q-Polynomial Group Association Schemes

✍ Masao Kiyota; Hiroshi Suzuki 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 114 KB

P- and Q-Polynomial Association Schemes

P- and Q-Polynomial Association Schemes and Their Antipodal P-Polynomial Covers

✍ Paul Terwilliger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 92 KB

We find a condition on the intersection numbers of any \(P\) - and \(Q\)-polynomial association scheme \(Y\) with diameter at least 3, that holds if \(Y\) has an antipodal \(P\)-polynomial cover with diameter at least 7. If \(Y\) is a known example of a \(P\) - and \(Q\)-polynomial association schem

Polynomial Time Approximation Schemes fo

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

✍ Sanjeev Arora; David Karger; Marek Karpinski 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 250 KB

We present a unified framework for designing polynomial time approximation schemes (PTASs) for ``dense'' instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By

On spherical designs obtained from Q-pol

On spherical designs obtained from Q-polynomial association schemes

✍ Sho Suda 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

We characterize that the image of the embedding of the Q-polynomial association scheme into the first eigenspace by primitive idempotent E 1 is a spherical t-design in terms of the Krein numbers. Furthermore, we show that the strengths of Pand Q-polynomial schemes as spherical designs are bounded by