All Questions

Consider a setting of $n$ buyers and $m$ goods. We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...

Question: what is known about the complexity of calculating the heaviest $k$-regular subgraph of a weighted symmetric graph if edge-weights can also be negative? Please note that in contrast to $k$-...

Given a finite graph $G(V,E)$ with undirected and weighted edges, whose set of vertices $V$ is partitioned into a collection $\mathfrak{P}=\lbrace V_1,\,\dots,\,V_k\rbrace$ of non-empty and pairwise ...