English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We consider domination analysis of approximation algorithms for the bipartiteboolean quadratic programming problem (BBQP) with m+n variables. A closed formformula is developed to compute the average objective function value A of allsolutions in O(mn) time. However, computing the median objective function valueof the solutions is shown to be NP-hard. Also, we show that any solution withobjective function value no worse than A dominates at least 2^{m+n-2} solutionsand this bound is the best possible. Further, we show that such a solution canbe identified in O(mn) time and hence the dominance ratio of this algorithm isat least 1/4. We then show that for any fixed rational number a > 1, nopolynomial time approximation algorithm exists for BBQP with dominance ratiolarger than 1-2^{(m+n)(1-a)/a}, unless P=NP. We then analyze some powerfullocal search algorithms and show that they can get trapped at a local maximumwith objective function value less than A. One of our approximation algorithmshas an interesting rounding property which provides a data dependent lowerbound on the optimal objective function value. A new integer programmingformulation of BBQP is also given and computational results with our roundingalgorithms are reported.

Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms