Submit to Algorithms Review for Algorithms Propose a Special Issue

Journal Menu

Journal Browser

Algorithms for Hard Problems: Approximation and Parameterization

Print Special Issue Flyer
Special Issue Editors
Special Issue Information
Keywords
Benefits of Publishing in a Special Issue
Published Papers

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Randomized, Online, and Approximation Algorithms".

Deadline for manuscript submissions: closed (31 March 2018) | Viewed by 24653

Share This Special Issue

Special Issue Editors

Prof. Dr. Juraj Hromkovic

E-Mail Website
Guest Editor

Department of Computer Science, ETH Zurich, Zürich, Switzerland
Interests: complexity theory; approximation algorithms; information content of computational problems; automata theory; computer science education

Dr. Hans-Joachim Böckenhauer

E-Mail Website
Guest Editor

Department of Computer Science, ETH Zurich, Zürich, Switzerland
Interests: online algorithms; approximation and reoptimization; parameterized algorithms

Dr. Dennis Komm

E-Mail Website
Guest Editor

Department of Computer Science, ETH Zurich, Zürich, Switzerland
Interests: online algorithms; advice complexity; approximation algorithms

Special Issue Information

Dear Colleagues,

Many optimization problems that are of interest for real-world applications are intractable from a worst-case point of view when requiring exact solutions. There are two very successful approaches to attack such computationally hard problems. On the one hand, approximation algorithms do not require to compute exact solutions, but guarantee solutions that are not too far away from the optimum. On the other hand, the time complexity of a fixed-parameter algorithm is polynomial in the input size, but potentially exponential in some parameter of the problem, which often is small for a large subclass of instances.

The open access journal Algorithms will host a Special Issue on “Algorithms for Hard Problems: Approximation and Parameterization”. The goal of the Special Issue is to collect new ideas and techniques related to the design and analysis of algorithms that follow the principles of approximation, parameterization, and any combination thereof.

Prof. Dr. Juraj Hromkovic
Dr. Hans-Joachim Böckenhauer
Dr. Dennis Komm
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

Approximation algorithms
Hardness of approximation
Reoptimization
Parameterized approximation algorithms
Parameterized complexity
fpt algorithms
Kernelization
Approximate kernels
Multivariate algorithmics
Stability of approximation

Benefits of Publishing in a Special Issue

Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (5 papers)

Download All Papers

Order results

Result details

Show export options Show export options

Select all

Export citation of selected articles as:

Research

17 pages, 368 KiB

Open AccessFeature PaperArticle

Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming

by Li-Hsuan Chen, Felix Reidl, Peter Rossmanith and Fernando Sánchez Villaamil

Algorithms 2018, 11(7), 98; https://doi.org/10.3390/a11070098 - 1 Jul 2018

Cited by 6 | Viewed by 4560

Abstract

Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this additional structure. On the negative side, we show with a novel approach that the space consumption of any (single-pass) dynamic programming algorithm on treedepth decompositions of depth d cannot be bounded by

{(2 - ϵ)}^{d} \cdot {log}^{O (1)} n

for Vertex Cover,

{(3 - ϵ)}^{d} \cdot {log}^{O (1)} n

for 3-Coloring and

{(3 - ϵ)}^{d} \cdot {log}^{O (1)} n

for Dominating Set for any

ϵ > 0

. This formalizes the common intuition that dynamic programming algorithms on graph decompositions necessarily consume a lot of space and complements known results of the time-complexity of problems restricted to low-treewidth classes. We then show that treedepth lends itself to the design of branching algorithms. Specifically, we design two novel algorithms for Dominating Set on graphs of treedepth d: A pure branching algorithm that runs in time

d^{O (d^{2})} \cdot n

and uses space

O (d^{3} log d + d log n)

and a hybrid of branching and dynamic programming that achieves a running time of

O (3^{d} log d \cdot n)

while using

O (2^{d} d log d + d log n)

space. Full article

(This article belongs to the Special Issue Algorithms for Hard Problems: Approximation and Parameterization)

► Show Figures

Figure 1

19 pages, 333 KiB

Open AccessArticle

Efficient Approximation for Restricted Biclique Cover Problems

by Alessandro Epasto and Eli Upfal

Algorithms 2018, 11(6), 84; https://doi.org/10.3390/a11060084 - 12 Jun 2018

Cited by 3 | Viewed by 5110

Abstract

Covering the edges of a bipartite graph by a minimum set of bipartite complete graphs (bicliques) is a basic graph theoretic problem, with numerous applications. In particular, it is used to characterize parsimonious models of a set of observations (each biclique corresponds to a factor or feature that relates the observations in the two sets of nodes connected by the biclique). The decision version of the minimum biclique cover problem is NP-Complete, and unless

P = N P

, the cover size cannot be approximated in general within less than a sub-linear factor of the number of nodes (or edges) in the graph. In this work, we consider two natural restrictions to the problem, motivated by practical applications. In the first case, we restrict the number of bicliques a node can belong to. We show that when this number is at least 5, the problem is still NP-hard. In contrast, we show that when nodes belong to no more than two bicliques, the problem has efficient approximations. The second model we consider corresponds to observing a set of independent samples from an unknown model, governed by a possibly large number of factors. The model is defined by a bipartite graph

G = (L, R, E)

, where each node in L is assigned to an arbitrary subset of up to a constant f factors, while the nodes in R (the independent observations) are assigned to random subsets of the set of k factors where k can grow with size of the graph. We show that this practical version of the biclique cover problem is amenable to efficient approximations. Full article

(This article belongs to the Special Issue Algorithms for Hard Problems: Approximation and Parameterization)

12 pages, 277 KiB

Open AccessArticle

Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems

by Rolf Klein, Christos Levcopoulos and Andrzej Lingas

Algorithms 2018, 11(4), 45; https://doi.org/10.3390/a11040045 - 11 Apr 2018

Cited by 5 | Viewed by 4334

Abstract

Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in

P \ R

, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are [...] Read more.

Let R denote a connected region inside a simple polygon, P. By building barriers (typically straight-line segments) in

P \ R

, we want to separate from R part(s) of P of maximum area. All edges of the boundary of P are assumed to be already constructed or natural barriers. In this paper we introduce two versions of this problem. In the budget fence version the region R is static, and there is an upper bound on the total length of barriers we may build. In the basic geometric firefighter version we assume that R represents a fire that is spreading over P at constant speed (varying speed can also be handled). Building a barrier takes time proportional to its length, and each barrier must be completed before the fire arrives. In this paper we are assuming that barriers are chosen from a given set B that satisfies certain conditions. Even for simple cases (e.g., P is a convex polygon and B the set of all diagonals), both problems are shown to be NP-hard. Our main result is an efficient ≈11.65 approximation algorithm for the firefighter problem, where the set B of allowed barriers is any set of straight-line segments with all endpoints on the boundary of P and pairwise disjoint interiors. Since this algorithm solves a much more general problem—a hybrid of scheduling and maximum coverage—it may find wider applications. We also provide a polynomial-time approximation scheme for the budget fence problem, for the case where barriers chosen from a set of straight-line cuts of the polygon must not cross. Full article

(This article belongs to the Special Issue Algorithms for Hard Problems: Approximation and Parameterization)

► Show Figures

Figure 1

11 pages, 272 KiB

Open AccessArticle

On Application of the Ray-Shooting Method for LQR via Static-Output-Feedback

by Yossi Peretz

Algorithms 2018, 11(1), 8; https://doi.org/10.3390/a11010008 - 16 Jan 2018

Cited by 7 | Viewed by 4559

Abstract

In this article we suggest a randomized algorithm for the LQR (Linear Quadratic Regulator) optimal-control problem via static-output-feedback. The suggested algorithm is based on the recently introduced randomized optimization method called the Ray-Shooting Method that efficiently solves the global minimization problem of continuous functions over compact non-convex unconnected regions. The algorithm presented here is a randomized algorithm with a proof of convergence in probability. Its practical implementation has good performance in terms of the quality of controllers obtained and the percentage of success. Full article

(This article belongs to the Special Issue Algorithms for Hard Problems: Approximation and Parameterization)

312 KiB

Open AccessArticle

Scheduling Non-Preemptible Jobs to Minimize Peak Demand

by Sean Yaw and Brendan Mumey

Algorithms 2017, 10(4), 122; https://doi.org/10.3390/a10040122 - 28 Oct 2017

Cited by 8 | Viewed by 5158

Abstract

This paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side scheduling can reduce these peaks by taking advantage of the fact that there is often flexibility in job start times. We focus attention on the case where the jobs are non-preemptible, meaning once started, they run to completion. The associated optimization problem is called the peak demand minimization problem, and has been previously shown to be NP-hard. Our results include an optimal fixed-parameter tractable algorithm, a polynomial-time approximation algorithm, as well as an effective heuristic that can also be used in an online setting of the problem. Simulation results show that these methods can reduce peak demand by up to 50% versus on-demand scheduling for household power jobs. Full article

(This article belongs to the Special Issue Algorithms for Hard Problems: Approximation and Parameterization)

► Show Figures

Journal Menu

Journal Browser

Algorithms for Hard Problems: Approximation and Parameterization

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (5 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI