Content deleted Content added
m WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (8855) |
m Bot: link syntax/spacing and minor changes |
||
Line 11:
## For every <math>S,X_1,X_2,\ldots,X_n\subseteq \Omega</math> such that <math>1_S\leq \sum_{i=1}^n \alpha_i 1_{S_i}</math> then we have that <math>f(S)\leq \sum_{i=1}^n \alpha_i f(S_i)</math>
## Let for each <math>i\in \{1,2,\ldots,m\}, a_i:\Omega\rightarrow \mathbb{R}_+</math> be linear set functions. Then <math>f(S)=\max_{i}\left(\sum_{x\in S}a_i(x)\right)</math>
# Functions based on [[set cover]]. Let <math>T_1,T_2,\ldots,T_m\subseteq \Omega</math> such that <math>\cup_{i=1}^m T_i=\Omega</math>. Then <math>f</math> is defined as follows
{{space|10}} <math>f(S)=\min t</math> such that there exists sets <math>T_{i_1},T_{i_2},\dots,T_{i_t}</math> satisfying <math>S\subseteq \cup_{j=1}^t T_{i_j}</math>
Line 24:
refs=
<ref name="UF">[[Uriel Feige|U. Feige]], On Maximizing Welfare when Utility Functions are Subadditive, SIAM J. Comput 39 (2009), pp. 122–142.</ref>
<ref name="DNS">S. Dobzinski, [[Noam Nisan|N. Nisan]],M. Schapira, Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders, Math. Oper. Res. 35 (2010), pp. 1–13.</ref>
}}
| |||