| 1. |
|
|
| 2. |
- Engebretsen, Lars
(author)
-
Bipartite multigraphs with expander-like properties
- 2007
-
In: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 155:13, s. 1667-1677
-
Journal article (peer-reviewed)abstract
- This note considers the following combinatorial question: "For which integers d and functions f(d) does there exist, for every large enough v, a bipartite d-regular multigraph on 2v nodes with node sets V and W having the following property: For every U that is a subset of either V or W, the cardinality of the set of neighbours of U is at least f(d)(vertical bar U vertical bar)?" Graphs with the above property seem to behave well also with respect to other, more complicated, expander-like properties. We provide results for d in (5,6,7,81 and give a description of a fairly general methodology for devising computer-assisted proofs for a wide class of mathematical claims using interval arithmetic.
|
|
| 3. |
- Engebretsen, Lars, et al.
(author)
-
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate
- 2006
-
In: Networks. - : Wiley. - 0028-3045 .- 1097-0037. ; 47:3, s. 172-177
-
Journal article (peer-reviewed)abstract
- Harmonic broadcasting was introduced by Juhn and Tseng in 1997 as a way to reduce the bandwidth requirements required for video-on-demand broadcasting. In this article, we note that harmonic broadcasting is actually a special case of the priority encoded transmission scheme introduced by Albanese et al. in 1996, and prove-using an information theoretic argument-that it is impossible to achieve the design goals of harmonic broadcasting using a shorter encoding.
|
|
| 4. |
- Engebretsen, Lars, et al.
(author)
-
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
- 2008
-
In: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 33:4, s. 497-514
-
Journal article (peer-reviewed)abstract
- Samorodnitsky and Trevisan [STOC 2000, pp. 191-199] proved that there exists, for every positive integer k, a PCP for NP with O(log n) randomness, query complexity 2k + k(2), free bit complexity 2k, completeness 1 - epsilon, and soundness 2(-k2) + epsilon. In this article, we devise a new "outer verifier," based on the layered label cover problem recently introduced by Dinur et al. [STOC 2003, pp. 595-601], and combine it with a new "inner verifier" that uses the query bits more efficiently than earlier verifiers. Our resulting theorem is that there exists, for every integer f >= 2, every positive integer t <= f (f - 1)/2, and every constant epsilon > 0, a PCP for NP with O(log n) randomness, query complexity f + t, free bit complexity f, completeness 1 - epsilon, and soundness 2(-t) + epsilon. As a corollary, there exists, for every integer q >= 3 and every constant epsilon > 0, a q-query PCP for NP with amortized query complexity 1 + root 2/q + epsilon-we also show in this article that combining our outer verifier with any natural candidate for a corresponding inner verifier gives a PCP that is kess query efficient than the one we obtain.
|
|
| 5. |
- Engebretsen, Lars, et al.
(author)
-
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- 2005
-
In: STACS 2005, PROCEEDINGS. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 3540249982 ; , s. 194-205
-
Conference paper (peer-reviewed)abstract
- In the PCP model, a verifier is supposed to probabilistically decide if a given input belongs to some language by posing queries to a purported proof of this fact. The probability that the verifier accepts an input in the language given a correct proof is called the completeness C; the probability that the verifier rejects an input not in the language given any proof is called the soundness s. For a verifier posing q queries to the proof, the amortized query complexity is defined by q/log(2) (c/s) if the proof is coded in binary. It is a measure of the average "efficiency" of the queries in the following sense: An ideal query should preserve the completeness and halve the soundness. If this were the case for all queries, the amortized query complexity would be exactly one. Samorodnitsky and Trevisan [STOC 2000] gave a q-query PCP for NP with amortized query complexity 1 + 2/root q + epsilon for any constant epsilon > 0. In this paper, we examine to what extent their result can be sharpened. Using the layered label cover problem recently introduced by Dinur et al. [STOC 2003], we devise a new "outer verifier" that allows us to construct an "inner verifier" that uses the query bits more efficiently than earlier verifiers. This enables us to construct a PCP for NP that queries q positions in the proof and has amortized query complexity 1 + root 2/q + epsilon. As an immediate corollary, we also obtain an improved hardness of approximation result for the Maximum q-CSP problem. Since the improvement compared to previous work is moderate, we then examine if there is an underlying reason for this. Our construction in this paper follows a paradigm for query efficient PCPs for NP outlined by many previous researchers and it combines a state-of-the-art "outer verifier" with a natural candidate for a query efficient "inner verifier". We prove in the full version of this paper that all natural attempts to construct more query efficient versions of our verifier are doomed to fail. This implies that significantly new ideas regarding proof composition and A encoding of PCP proofs are required to construct PCPs for NP that are more query efficient than the one we propose in his paper.
|
|
| 6. |
- Engebretsen, Lars
(author)
-
Platform-independent code conversion within the C++ locale framework
- 2006
-
In: Software, practice & experience. - : Wiley. - 0038-0644 .- 1097-024X. ; 36:15, s. 1643-1654
-
Journal article (peer-reviewed)abstract
- This paper describes some of the author's experiences from a C++ implementation of a concordance program for texts in Old West Norse (also known as Old Icelandic) and Runic Swedish. Since the input to the program used a character repertoire that no standard one-byte character encoding covers, it was natural to use Unicode to represent data both inside the program and in external files. Inside the program, each character was represented with C++ 'wide characters'; the input and output was represented in UTF-8. The author constructed C++ code conversion facets that convert data between those two representations during file I/O. This enabled him to successfully compile, and run, the concordance program on both Linux (Fedora Core 3 with gcc 3.4.2) and Windows XP (using Visual C++ NET 2003). The only necessary change to the source when changing platform was isolated to the lines selecting which code conversion facet to use-all other pieces of code remained unchanged. In particular, the author could still use the standard C++ locale framework for collation and code conversion, in spite of the fact that the library-provided code conversion facets had been replaced.
|
|
| 7. |
- Engebretsen, Lars, et al.
(author)
-
Three-query PCPs with perfect completeness over non-Boolean domains
- 2005
-
In: Random structures & algorithms (Print). - : Wiley. - 1042-9832 .- 1098-2418. ; 27:1, s. 46-75
-
Journal article (peer-reviewed)abstract
- We study non-Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d >= 2, we construct a nonadaptive PCP with perfect completeness and soundness d(-1) + d(-2) + epsilon, for any constant epsilon > 0, and an adaptive PCP with perfect cornpleteness and soundness d(-1) + epsilon, for any constant epsilon > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d(-1) + epsilon, for any constant epsilon > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proof's also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold.
|
|
| 8. |
- Engebretsen, Lars, et al.
(author)
-
TSP with bounded metrics
- 2006
-
In: Journal of computer and system sciences (Print). - : Elsevier BV. - 0022-0000 .- 1090-2724. ; 72:4, s. 509-546
-
Journal article (peer-reviewed)abstract
- The general asymmetric TSP with triangle inequality is known to be approximable only within logarithmic factors. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics, i.e., metrics where the distances are integers between one and some constant upper bound. In this case, the problem is known to be approximable within a constant factor. We prove that it is NP-hard to approximate the asymmetric TSP with distances one and two within 321/320 - epsilon and that it is NP-hard to approximate the symmetric TSP with distances one and two within 741/740 - epsilon for every constant epsilon > 0. Recently, Papadimitriou and Vempala announced improved approximation hardness results for both symmetric and asymmetric TSP with graph metric. We show that a similar construction can be used to obtain only slightly weaker approximation hardness results for TSP with triangle inequality and distances that are integers between one and eight. This shows that the Papadimitriou-Vempala construction is "local" in nature and, intuitively, indicates that it cannot be used to obtain hardness factors that grow with the size of the instance.
|
|
| 9. |
- Hägglund, Martin, 1976-
(author)
-
Epidemiology and prevention of football injuries
- 2007
-
Doctoral thesis (other academic/artistic)abstract
- The aims of this thesis were to study the incidence, severity and pattern of injury in male and female elite football players; to study time trends in injury risk; to identify risk factors for injury; and to test the effectiveness of an intervention programme aimed at preventing re-injury.All studies followed a prospective design using standardised definitions and data collection forms. Individual training and match exposure was registered for all players participating. Time loss injuries were documented by each team’s medical staff.The amount of training increased by 68% between the 1982 and 2001 Swedish top male division seasons, reflecting the shift from semi-professionalism to full professionalism. No difference in injury incidence or injury severity was found between seasons. The injury incidence was 4.6 vs. 5.2/1000 training hours and 20.6 vs. 25.9/1000 match hours. The incidence of severe injury (absence >4 weeks) was 0.8/1000 hours in both seasons.The Swedish and Danish top male divisions were followed during the spring season of 2001. A higher risk for training injury (11.8 vs. 6.0/1000 hours, p<0.01) and severe injury (1.8 vs. 0.7/1000 hours, p=0.002) was observed among the Danish players. Re-injury accounted for 30% and 24% of injuries in Denmark and Sweden respectively.The Swedish top male division was studied over two consecutive seasons, 2001 and 2002, and comparison of training and match injury incidences between seasons showed similar results. Players who were injured in the 2001 season were at greater risk for injury in the following season compared to non-injured players (relative risk 2.7; 95% CI 1.7-4.3). Players with a previous hamstring injury, groin injury and knee joint trauma were two to three times more likely to suffer an identical injury to the same limb in the following season, but no such relationship was found for ankle sprain. Age was not associated with an increased injury risk.The effectiveness of a coach-controlled rehabilitation programme on the rate of re-injury was studied in a randomised controlled trial at amateur male level. In the control group, 23 of 79 injured players suffered a recurrence during the season compared to 10 of 90 players in the intervention group. There was a 75% lower re-injury risk in the intervention group for lower limb injuries (relative risk 0.25; 95% CI 0.11-0.57). The preventive effect was greatest during the first weeks after return to play.Both the male and female Swedish top divisions were followed during the 2005 season. Male elite players had a higher risk for training injury (4.7 vs. 3.8/1000 hours, p<0.05) and match injury (28.1 vs. 16.1/1000 hours, p<0.001) than women. However, no difference was observed in the rate of severe injury (0.7/1000 hours in both groups). The thigh was the most common site of injury in both men and women, while injury to the hip/groin was more frequent in men and to the knee in women. Knee sprain accounted for 31% and 37% of the time lost from training and match play in men and women respectively.
|
|
| 10. |
- Palbom, Anna, 1971-
(author)
-
On Approximating Asymmetric TSP and Related Problems
- 2006
-
Licentiate thesis (other academic/artistic)abstract
- In this thesis we study problems related to approximation of asymmetric TSP. First we give worst case examples for the famous algorithm due to Frieze, Gabiati and Maffioli for asymmetric TSP with triangle inequality. Some steps in the algorithm consist of arbitrary choices. To prove lower bounds, these choices need to be specified. We show a worst case performance with some deterministic assumptions on the algorithm and then prove an expected worst case performance for a randomised version of the algorithm. The algorithm by Frieze et al. produces a spanning cactus and makes a TSP tour by shortcuts. We have proven that determining if there is a spanning cactus in a general asymmetric graph is an NP-complete problem and that finding a minimum spanning cactus in a complete, directed graph with triangle inequality is equivalent to finding the TSP tour and the problems are equally hard to approximate. We also give three other results; we show a connection between asymmetric TSP and TSP in a bipartite graph, we show that it is NP-hard to find a cycle cover in a bipartite graph without cycles of length six or less and finally we present some results for a new problem with ordered points on the circle.
|
|
