Name
Abstract | ||
|---|---|---|
We introduce a class of pseudo-Boolean functions called ordered, symmetric half-products. The class includes a number of well known scheduling problems. We study sets of dominating solutions for minimization of the half-products, and we show their fully polynomial time approximation schemes that use a natural rounding scheme to obtain ε-solutions in O(n2/ε) time. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.dam.2004.07.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
natural rounding scheme,polynomial time approximation scheme,scheduling,pseudo-boolean functions,half-products,fully polynomial time approximation schemes,pseudo-boolean function,symmetric half-products,optimization,fully polynomial time approximation scheme | Discrete mathematics,Symmetric function,Combinatorics,Dominating set,Scheduling (computing),Rounding,Minimisation (psychology),Minification,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
146 | 3 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 0.82 | 17 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wieslaw Kubiak | 1 | 540 | 62.61 |