One of the approaches in solving NP-hard problems is through reoptimization. In this technique, we solve a locally modified instance of a problem by making use of known solution to its original instance instead of obt...
详细信息
ISBN:
(纸本)9789881925251
One of the approaches in solving NP-hard problems is through reoptimization. In this technique, we solve a locally modified instance of a problem by making use of known solution to its original instance instead of obtaining a solution from scratch. In this paper, we present a reoptimization of motif finding problem. Since the problem is showed to be self-reducible, we can use a self-reduction method to solve the reoptimization variant of the problem. Using the method, we have improved the approximation ratio of the algorithm solving the reoptimized version as compared to the non-reoptimized counterpart. Moreover, we showed that if a certain problem is self-reducible, any problem that obtains a polynomial-time reduction to it is also self-reducible.
In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move ...
详细信息
A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of u...
详细信息
Beam search (BS) is a well-known graph search algorithm frequently used to heuristically find good or near-optimal solutions to combinatorial optimization problems. Its most crucial component is a heuristic function t...
详细信息
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms an...
详细信息
A general framework for the use of two-party communication protocols for lower bound proofs on multilective computations was developed. The result not only created a transparent presentation of some known lower bounds...
详细信息
A general framework for the use of two-party communication protocols for lower bound proofs on multilective computations was developed. The result not only created a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits. Another advantage of this framework is that it provides lower bounds for a lot of concrete functions.
In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the numbe...
详细信息
We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local curr...
详细信息
We present a numerical study of multicommodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multistable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena.
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, includin...
详细信息
Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. ...
详细信息
暂无评论