liu.seSearch for publications in DiVA

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt145",{id:"formSmash:upper:j_idt145",widgetVar:"widget_formSmash_upper_j_idt145",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt146_j_idt148",{id:"formSmash:upper:j_idt146:j_idt148",widgetVar:"widget_formSmash_upper_j_idt146_j_idt148",target:"formSmash:upper:j_idt146:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

A randomised approximation algorithm for the hitting set problemPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2014 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 555, 23-34 p.Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier , 2014. Vol. 555, 23-34 p.
##### Keyword [en]

Approximation algorithms; Probabilistic methods; Randomised rounding; Hitting set; Vertex cover; Greedy algorithms
##### National Category

Computer and Information Science Mathematics
##### Identifiers

URN: urn:nbn:se:liu:diva-112302DOI: 10.1016/j.tcs.2014.03.029ISI: 000343627600004OAI: oai:DiVA.org:liu-112302DiVA: diva2:765671
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt375",{id:"formSmash:j_idt375",widgetVar:"widget_formSmash_j_idt375",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt381",{id:"formSmash:j_idt381",widgetVar:"widget_formSmash_j_idt381",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt387",{id:"formSmash:j_idt387",widgetVar:"widget_formSmash_j_idt387",multiple:true});
Available from: 2014-11-24 Created: 2014-11-24 Last updated: 2015-10-02

Let H = (V, epsilon) be a hypergraph with vertex set V and edge set epsilon, where n := vertical bar V vertical bar and m := vertical bar epsilon vertical bar. Let l be the maximum size of an edge and Delta be the maximum vertex degree. A hitting set (or vertex cover) in H is a subset of V in which all edges are incident. The hitting set problem is to find a hitting set of minimum cardinality. It is known that an approximation ratio of l can be achieved easily. On the other hand, for constant l, an approximation ratio better than l cannot be achieved in polynomial time under the unique games conjecture (Khot and Regev, 2008 [17]). Thus breaking the l-barrier for significant classes of hypergraphs is a complexity-theoretically and algorithmically interesting problem, which has been studied by several authors (Krivelevich, 1997 [18], Halperin, 2000 [12], Okun, 2005 [23]). We propose a randomised algorithm of hybrid type for the hitting set problem, which combines LP-based randomised rounding, graphs sparsening and greedy repairing and analyse it for different classes of hypergraphs. For hypergraphs with Delta = O(n1/4) and l = O (root n) we achieve an approximation ratio of l(1 - c/Delta), for some constant c greater than 0, with constant probability. For the case of hypergraphs where l and Delta are constants, we prove a ratio of l(1 - l-1/8 Delta). The latter is done by analysing the expected size of the hitting set and using concentration inequalities. Moreover, for quasi-regularisable hypergraphs, we achieve an approximation ratio of l(1 - n/8m). We show how and when our results improve over the results of Krivelevich, Halperin and Okun.

References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1080",{id:"formSmash:lower:j_idt1080",widgetVar:"widget_formSmash_lower_j_idt1080",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1081_j_idt1083",{id:"formSmash:lower:j_idt1081:j_idt1083",widgetVar:"widget_formSmash_lower_j_idt1081_j_idt1083",target:"formSmash:lower:j_idt1081:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});